根据广为流传的说法，程序员喝大量的咖啡，却只认识几个单词。一个典型程序员的词汇量仅由三个单词组成。此外，他们很少知道如何拼写这些单词。为了帮助程序员纠正拼写错误，我们出版了一本名为《每个典型程序员都应该知道的三个单词词典》的书。

你得到了一本这样的书，但不久之后，你不小心把咖啡洒在了上面。现在，你无法辨认其中的一些字符。幸运的是，这三个单词像字典中通常的情况一样，是互不相同的，并且按字典序排列。

在你尝试利用这一事实来恢复缺失的字符之前，你想知道有多少种不同的恢复方式。由于你预计这个数字可能很大，你希望求出它对 $10^9 + 9$ 取模后的结果。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各测试用例的描述：

每个测试用例包含三行，每行包含一个非空单词，按它们在字典中出现的顺序排列。单词由小写英文字母和问号组成，问号表示缺失的字符。每个单词的长度不超过 $1\,000\,000$。输入文件大小不超过 $16.0\text{ MiB}$。

输出格式

对于每个测试用例，输出一行，包含将每个问号替换为 'a' 到 'z' 之间的字母，使得这三个单词互不相同且按字典序排列的不同方案数。结果需对 $10^9 + 9$ 取模。

样例

样例输入 1

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

样例输出 1

42562
52
1