시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB18121292.308%

문제

Someone put a physical mirror in the holodeck chamber, and it has scrambled some critical simulation data! The mirror had the effect of superimposing reversed data on top of the original data. You need to figure out how scrambled the data is.

Given a positive number Y , calculate the number of distinct positive values of X such that Y = X + rev(X). The rev operator reverses the digits of a number. The values for X must be in their normal decimal form, without leading zeros. For example, rev(350) = 53 and rev(53) = 35.

입력

Input begins with a line with one integer T (1 ≤ T ≤ 500) denoting the number of test cases. Each test case consists of a single line with a single integer Y (1 ≤ Y < 1018).

출력

For each test case, print out a line containing the count of positive integers that, when summed with their reverse, equals the input value.

예제 입력 1

8
10
11
121
299999999999999981
109
7087
59284
10201

예제 출력 1

1
1
9
1
0
0
0
1