Garou is known for hunting heroes and numbers. Tareo, who is constantly looking for a way to impress "uncle" Garou finally decides to impress him with the following problem:

Given a positive integer \(N\), find out how many positive integers \(X\) satisfy the equation \(X + S(X) + S(S(X)) = N\), where \(S(X)\) denotes sum of digits of \(X\) in decimal representation.

Garou is generally quite good at taking down these kinds of problems, but today he got stuck at this one and is looking for some help. Can you help him solve the problem? He may teach you some martial arts (maybe even the legendary Water Stream Rock Smashing Fist technique!) 

Input

The first line of the input contains a single integer \(T\) denoting the number of test cases to follow. Description of each test case contains a single integer \(N\).

Output

For each test case, output a single line denoting the count of number of positive integers \(X\) satisfying the above given equation.

Constraints

\(1 \le T \le 10^4\)

\(1 \le N \le 10^9\)