C. Lucky Numbers
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

We know that O–O read books everyday. He learned about lucky numbers.

If their decimal representation doesn't contain digits other than $$$4$$$ and $$$7$$$. For example, numbers $$$47, 744, 4$$$ are lucky and $$$5, 17, 467$$$ are not.

Now, he has the large number $$$n$$$, his task is to find the number of lucky numbers not greater than $$$n$$$.

Print it modulo 998244353.

The number doesn't have leading zeroes.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The description of the test cases follows.

The each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^{100})$$$.

Output

For each test case, output a single integer.

Example
Input
3
47
748
774411
Output
4
12
110