Segundo uma crença popular, os programadores bebem muito café e conhecem poucas palavras. O vocabulário de um programador típico consiste em apenas três palavras. Além disso, ele raramente sabe como escrevê-las. Para ajudar os programadores com os seus erros ortográficos, publicámos um livro intitulado «O Dicionário das Três Palavras que Todo o Programador Típico Deve Conhecer».

Obtiveste um exemplar do livro, mas pouco depois entornaste café sobre ele. Agora, não consegues ler alguns dos caracteres. Felizmente, as três palavras eram, como é habitual nos dicionários, distintas e estavam impressas por ordem lexicográfica.

Antes de tentares usar esse facto para recuperar os caracteres em falta, queres saber de quantas maneiras diferentes o podes fazer. Como esperas que esse número possa ser grande, queres conhecê-lo módulo $10^9 + 9$.

Entrada

A primeira linha da entrada contém o número de casos de teste $T$. Seguem-se as descrições dos casos de teste:

Cada caso de teste consiste em três linhas, cada uma contendo uma única palavra não vazia, pela ordem em que aparecem no dicionário. As palavras consistem em letras minúsculas do alfabeto inglês e aspas, sendo estas últimas usadas para indicar os caracteres em falta. Cada palavra tem, no máximo, $1\,000\,000$ caracteres.

O tamanho do ficheiro de entrada não excede 16.0 MiB.

Saída

Para cada caso de teste, escreve uma linha com o número de maneiras diferentes de substituir cada ponto de interrogação por uma das 26 letras de «a» a «z», de modo que as três palavras sejam distintas e estejam por ordem lexicográfica. O número deve ser apresentado módulo $10^9 + 9$.

Exemplos

Entrada 1

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

Saída 1

42562
52
1