King Sam loves to play with numbers. This time he came to know about an amazing function F(x) which sums digits of a number 'x'. For example, when x = 2344, F(x) = 13. Now using composite function, he created a problem.

Given a positive integer N, find out how many positive integers X satisfy the equation

X + F(X) + F(F(X)) + ..... + till (F(X) = X) = N .

Input Format:

The first line of input contains an integer T , no. of test-cases. Each of next T lines contain one integer number N.

Output Format:

Output single integer in a line denoting the count of number of positive integers X satisfying the above given equation for each test-case.

Constraints:

1<= T <=10^4

1<= N <=10^15