C. Carrying Conundrum
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice has just learned addition. However, she hasn't learned the concept of "carrying" fully — instead of carrying to the next column, she carries to the column two columns to the left.

For example, the regular way to evaluate the sum $2039 + 2976$ would be as shown:

However, Alice evaluates it as shown:

In particular, this is what she does:

• add $9$ and $6$ to make $15$, and carry the $1$ to the column two columns to the left, i. e. to the column "$0$ $9$";
• add $3$ and $7$ to make $10$ and carry the $1$ to the column two columns to the left, i. e. to the column "$2$ $2$";
• add $1$, $0$, and $9$ to make $10$ and carry the $1$ to the column two columns to the left, i. e. to the column above the plus sign;
• add $1$, $2$ and $2$ to make $5$;
• add $1$ to make $1$.
Thus, she ends up with the incorrect result of $15005$.

Alice comes up to Bob and says that she has added two numbers to get a result of $n$. However, Bob knows that Alice adds in her own way. Help Bob find the number of ordered pairs of positive integers such that when Alice adds them, she will get a result of $n$. Note that pairs $(a, b)$ and $(b, a)$ are considered different if $a \ne b$.

Input

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.

The only line of each test case contains an integer $n$ ($2 \leq n \leq 10^9$) — the number Alice shows Bob.

Output

For each test case, output one integer — the number of ordered pairs of positive integers such that when Alice adds them, she will get a result of $n$.

Example
Input
5
100
12
8
2021
10000

Output
9
4
7
44
99

Note

In the first test case, when Alice evaluates any of the sums $1 + 9$, $2 + 8$, $3 + 7$, $4 + 6$, $5 + 5$, $6 + 4$, $7 + 3$, $8 + 2$, or $9 + 1$, she will get a result of $100$. The picture below shows how Alice evaluates $6 + 4$: