Giải bài trực tuyến

Cho số tự nhiên N <= 10^18. Đếm xem có bao nhiêu cặp (A,B) thỏa mãn:

A + B = N

B là số đảo của A

Số đảo của 110 là 11

Số đảo của 123 là 321

Chú ý: cặp (123,321) và cặp (321,123) là 2 cặp khác nhau

Input

Dòng đầu gồm 1 số M chỉ số lượng test

M dòng sau, mỗi dòng gồm 1 số nguyên dương N ( N <= 10^18 )

Output

Gồm M dòng, là kết quả tương ứng với từng test

Example

Input:
4

10

11

121

22

10
Output:
1

1

9

2

Giải thích:
Với N=9 có các cặp sau:
110 11
92 29
83 38
74 47
65 56
56 65
47 74
38 83
29 92