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

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

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

输入格式

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

每个测试用例包含三行，每行包含一个非空单词——按它们在字典中出现的顺序排列。单词由小写英文字母和问号组成，问号表示缺失的字符。每个单词的长度最多为 $1\,000\,000$。

输出格式

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

样例

输入 1

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

输出 1

42562
52
1