A postive integer A is called a "palindrome number" if the reverse of the decimal representaion is the same as the original one. Ex. 13231 is a palindrome number, but 13333 is not.

Given a number A(1 <= A <= 1e18), find the number of pairs (a,b) such that a,b are both palindrome numbers, and the sum of a and b is A.

If A is 391, there are 6 ways: 8 + 383 = 383 + 8 = 391 88 + 303 = 303 + 88 = 391 99 + 292 = 292 + 99 = 391

Input

The first Line contains the number of test cases T <= 10. Each test case contains a number A.

Output

Output the number of ways.

Example

Input:
1
391

Output:
6