За поширеною думкою, програмісти п’ють багато кави й знають лише кілька слів. Словниковий запас типового програміста складається лише з трьох слів. До того ж він рідко знає, як їх правильно писати. Щоб допомогти програмістам з орфографічними помилками, ми видали книжку під назвою «Словник трьох слів, які має знати кожен типовий програміст».

Ви отримали примірник цієї книжки, але невдовзі пролили на нього каву. Тепер деякі символи неможливо прочитати. На щастя, ці три слова, як зазвичай у словниках, були різними й надрукованими в лексикографічному порядку.

Перш ніж спробувати скористатися цим фактом для відновлення втрачених символів, ви хочете дізнатися, скількома різними способами це можна зробити. Оскільки ви очікуєте, що це число може бути великим, ви хочете знати його за модулем $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