Według powszechnego przekonania programiści piją dużo kawy i znają tylko kilka słów. Słownictwo typowego programisty składa się z zaledwie trzech słów. Co więcej, rzadko wie on, jak się je pisze. Aby pomóc programistom z błędami w pisowni, wydaliśmy książkę zatytułowaną „Słownik trzech słów, które każdy typowy programista powinien znać”.

Zdobyłeś egzemplarz tej książki, lecz wkrótce potem wylałeś na niego kawę. Teraz nie możesz odczytać niektórych znaków. Na szczęście te trzy słowa były, jak zwykle w słownikach, różne i wydrukowane w porządku leksykograficznym.

Zanim spróbujesz wykorzystać ten fakt do odtworzenia brakujących znaków, chcesz wiedzieć, na ile różnych sposobów można to zrobić. Ponieważ spodziewasz się, że ta liczba może być duża, chcesz znać ją modulo $10^9 + 9$.

Wejście

Pierwszy wiersz wejścia zawiera liczbę przypadków testowych $T$. Dalej następują ich opisy:

Każdy przypadek testowy składa się z trzech wierszy, z których każdy zawiera jedno niepuste słowo, w kolejności ich występowania w słowniku. Słowa składają się z małych liter alfabetu angielskiego i cudzysłowów, przy czym te ostatnie oznaczają brakujące znaki. Każde słowo ma co najwyżej $1\,000\,000$ znaków.

Rozmiar pliku wejściowego nie przekracza 16.0 MiB.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający liczbę różnych sposobów zastąpienia każdego znaku zapytania jedną z 26 liter od „a” do „z” tak, aby trzy słowa były różne i uporządkowane leksykograficznie. Liczbę należy wypisać modulo $10^9 + 9$.

Przykład

Wejście 1

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

Wyjście 1

42562
52
1