Según una creencia popular, los programadores beben mucho café y conocen pocas palabras. El vocabulario de un programador típico consta de solo tres palabras. Además, rara vez sabe cómo se escriben. Para ayudar a los programadores con sus errores ortográficos, publicamos un libro titulado «El diccionario de las tres palabras que todo programador típico debería conocer».

Conseguiste un ejemplar del libro, pero poco después derramaste café sobre él. Ahora no puedes leer algunos de los caracteres. Por suerte, las tres palabras eran, como suele ocurrir en los diccionarios, distintas y estaban impresas en orden lexicográfico.

Antes de intentar aprovechar ese hecho para recuperar los caracteres que faltan, quieres saber de cuántas maneras diferentes puedes hacerlo. Como esperas que ese número pueda ser grande, quieres conocerlo módulo $10^9 + 9$.

Entrada

La primera línea de la entrada contiene el número de casos de prueba $T$. A continuación se describen los casos de prueba:

Cada caso de prueba consta de tres líneas, cada una con una única palabra no vacía, en el orden en que aparecen en el diccionario. Las palabras constan de letras minúsculas del alfabeto inglés y comillas; estas últimas indican los caracteres que faltan. Cada palabra tiene como máximo $1\,000\,000$ caracteres.

El tamaño del archivo de entrada no supera los 16.0 MiB.

Salida

Para cada caso de prueba, imprime una línea con el número de maneras diferentes de sustituir cada signo de interrogación por una de las 26 letras de «a» a «z», de modo que las tres palabras sean distintas y estén en orden lexicográfico. El número debe imprimirse módulo $10^9 + 9$.

Ejemplos

Entrada 1

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

Salida 1

42562
52
1