Cho số tự nhiên ~N \le 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 \le 10^{18})~

Output

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

Sample Input

4
10
11
121
22

Sample Output

1
1
9
2

Note

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~