Selon une croyance populaire, les programmeurs boivent beaucoup de café et ne connaissent que quelques mots. Le vocabulaire d’un programmeur typique ne comporte que trois mots. De plus, il sait rarement comment les écrire. Pour aider les programmeurs à corriger leurs fautes d’orthographe, nous avons publié un livre intitulé « Le dictionnaire des trois mots que tout programmeur typique devrait connaître ».

Vous avez obtenu un exemplaire de ce livre, mais peu après, vous avez renversé votre café dessus. Vous ne pouvez désormais plus lire certains caractères. Heureusement, les trois mots étaient, comme c’est l’usage dans les dictionnaires, distincts et imprimés dans l’ordre lexicographique.

Avant d’essayer d’utiliser ce fait pour retrouver les caractères manquants, vous voulez savoir de combien de façons différentes vous pouvez le faire. Comme vous vous attendez à ce que ce nombre puisse être grand, vous voulez le connaître modulo $10^9 + 9$.

Entrée

La première ligne de l’entrée contient le nombre de cas de test $T$. Les descriptions des cas de test suivent :

Chaque cas de test comprend trois lignes, chacune contenant un seul mot non vide, dans l’ordre où ils apparaissent dans le dictionnaire. Les mots sont constitués de lettres minuscules de l’alphabet anglais et de guillemets, ces derniers indiquant les caractères manquants. Chaque mot comporte au plus $1\,000\,000$ caractères.

La taille du fichier d’entrée ne dépasse pas 16.0 MiB.

Sortie

Pour chaque cas de test, affichez une ligne contenant le nombre de façons différentes de remplacer chaque point d’interrogation par l’une des 26 lettres de « a » à « z », de sorte que les trois mots soient distincts et dans l’ordre lexicographique. Le nombre doit être affiché modulo $10^9 + 9$.

Exemples

Entrée 1

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

Sortie 1

42562
52
1