Vocabulary

A running joke says that a programmer drinks a lot of coffee and knows only three words. On top of that, the programmer rarely spells them right. So we published a dictionary that holds just those three words.

You got a copy, and soon after that you spilled your coffee over it. Some characters are now unreadable. Luckily the three words are distinct and, as a dictionary does, printed in lexicographic order.

Before you use that fact to recover the missing characters, you want to know in how many ways you can do it. That number can be large, so compute it modulo $10^9 + 9$.

The first line contains the number of test cases $T$. The test cases follow.

Each test case consists of three lines, and each line contains one nonempty word, in the order the words appear in the dictionary. A word consists of lowercase English letters and question marks, where a question mark stands for an unreadable character. Each word is at most 1,000,000 characters long.

For each test case, print one line with the answer. The answer is the number of ways to replace every question mark with one of the 26 letters from a to z so that the three words are distinct and in lexicographic order, taken modulo $10^9 + 9$.