Согласно распространённому мнению, программисты пьют много кофе и знают лишь несколько слов. Словарный запас типичного программиста состоит всего из трёх слов. Кроме того, он редко знает, как они пишутся. Чтобы помочь программистам с орфографическими ошибками, мы издали книгу под названием «Словарь трёх слов, которые должен знать каждый типичный программист».

Вы получили экземпляр этой книги, но вскоре пролили на него кофе. Теперь некоторые символы невозможно прочитать. К счастью, эти три слова, как обычно бывает в словарях, были различны и напечатаны в лексикографическом порядке.

Прежде чем попытаться воспользоваться этим фактом для восстановления пропавших символов, вы хотите узнать, сколькими различными способами это можно сделать. Поскольку вы ожидаете, что число может быть большим, вы хотите узнать его по модулю $10^9 + 9$.

Входные данные

Первая строка входных данных содержит количество тестовых случаев $T$. Далее следуют описания тестовых случаев:

Каждый тестовый случай состоит из трёх строк, каждая из которых содержит одно непустое слово, в порядке их появления в словаре. Слова состоят из строчных букв английского алфавита и кавычек, причём последние обозначают пропавшие символы. Длина каждого слова не превышает $1\,000\,000$ символов.

Размер входного файла не превышает 16.0 MiB.

Выходные данные

Для каждого тестового случая выведите одну строку с количеством различных способов заменить каждый вопросительный знак одной из 26 букв от «a» до «z» так, чтобы три слова были различны и располагались в лексикографическом порядке. Число следует вывести по модулю $10^9 + 9$.

Примеры

Входные данные 1

3
?heoret?cal
c?mputer
?cience
jagiellonian
?niversity
kra?ow
?
b
c

Выходные данные 1

42562
52
1