L. AL-1S
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The name of Tendou "Alice" Aris originates from the misinterpretation of her identifier AL-1S, when Saiba Momoi misread the digit 1 as the uppercase letter I. This confusion arises because the characters l (lowercase L), I (uppercase i), and 1 (digit one) look annoyingly similar. Unfortunately, there's no way to prevent all three—l, I, and 1—from appearing together in the same string. That's why her maid Key decided to lay down some strict rules to avoid potential misinterpretation.

A string $$$s$$$ is said to be approved by Key if it satisfies all of the following:

  • l, I, and 1 must not appear at the beginning or end of the string.
  • Every digit 1 can be only adjacent to digits.
  • Every letter l can be only adjacent to lowercase letters.
  • Every letter I can be only adjacent to uppercase letters.

For example:

  • "abclllz2113AabCIIXYZ" is approved.
  • "1abcd", "AbcllZ", and "ABCDI" are disapproved.

You're given a string $$$s$$$ that may contain some ? characters. You need to replace each ? with a Latin letter or digit so that the resulting string is approved by Key. Count the number of valid completions. Since the result can be too large, you only need to answer the result modulo $$$998244353$$$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The single line of each test case contains one string $$$s$$$ ($$$1\le|s|\le10^6$$$). It is guaranteed that $$$s$$$ contains only Latin characters, digits, and question marks.

It is guaranteed that the sum of $$$|s|$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output one integer — the number of strings approved by Key modulo $$$998244353$$$.

Example
Input
4
?
???
ai???IZ
??I
Output
59
206710
89775
0