Problem D: Magical Number

Problem D: Magical Number

Time Limit: 4 Sec  Memory Limit: 256 MB
Submit: 1407  Solved: 198
[Submit][Status][Web Board]

Description

We want to find those Magical Numbers which are symmetry, that is, no matter whether you count it from left to right or right to left, its value will not be changed. For example, 1, 121, 12321, are Magic Numbers, but 123, 321, are not. To be more precise, suppose that we present a number by array a of size n( index starts with 1). It is a Magical Number if and only if a[i]=a[n-i+1] for any i, 1<=i<=n. Notice that Magical Number are non-negative integers.

You are asked to count how many Magical Numers are smaller or equal than an integer N.

Input

The first line of input is the number of test cases T (1<=T<=20) 
For each test case, there is only one integer N(0<=N<=1011)

Notice that: the maximum value of a signed 32-bit integer is 2147483647
'long long' in C++, 'long' in Java is recommended.

Output

One line for each test case, print the result you get.

Sample Input

2
1
11

Sample Output

2
11

HINT

Try to construct all the required Magical Numbers rather than check it from 1 to N.

[Submit][Status]