世間では、プログラマーはコーヒーをたくさん飲み、わずかな単語しか知らないと言われています。典型的なプログラマーの語彙は、たった三つの単語からなります。しかも、それらの綴りを知っていることはめったにありません。プログラマーの綴り間違いを助けるため、私たちは『典型的なプログラマーなら誰もが知っておくべき三つの単語の辞書』という本を出版しました。

あなたはこの本を一冊手に入れましたが、そのすぐ後にコーヒーをこぼしてしまいました。今では一部の文字が読めません。幸い、この三つの単語は普通の辞書と同様に、互いに異なり、辞書順に印刷されていました。

この事実を使って欠けた文字を復元しようとする前に、復元方法が何通りあるか知りたいと思っています。その数は大きくなるかもしれないので、$10^9 + 9$ で割った余りを求めてください。

入力

入力の最初の行にはテストケース数 $T$ が与えられます。続いて各テストケースの説明が与えられます。

各テストケースは三行からなり、各行には空でない単語が一つずつ、辞書に現れる順序で与えられます。単語は英小文字と引用符からなり、後者は欠けた文字を表します。各単語の長さは $1\,000\,000$ 文字以下です。

入力ファイルのサイズは 16.0 MiB 以下です。

出力

各テストケースについて、各疑問符を「a」から「z」までの 26 文字のいずれかで置き換え、三つの単語が互いに異なり辞書順になるようにする方法の数を一行に出力してください。個数は $10^9 + 9$ で割った余りとして出力してください。

入出力例

入力 1

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

出力 1

42562
52
1