For an integer $x$, we call another integer $y$ friendly if the following condition holds:

• $y - d(y) = x$, where $d(y)$ is the sum of the digits of $y$.

For a given integer $x$, determine how many friendly numbers it has.

Input

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

Each test case consists of a single line containing one integer $x$ ($1 \le x \le 10^{9}$).

Output

For each test case, output one integer — the answer to the problem.

Note

The number $1$ does not have any friendly numbers.

The number $18$ has $10$ friendly numbers: These are all the numbers from $20$ to $29$. For example, $20 - d(20) = 20 - 2 = 18$.

The number $998\,244\,360$ has $10$ friendly numbers:

• $998\,244\,400$
• $998\,244\,401$
• $998\,244\,402$
• $998\,244\,403$
• $998\,244\,404$
• $998\,244\,405$
• $998\,244\,406$
• $998\,244\,407$
• $998\,244\,408$
• $998\,244\,409$