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.

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<=10¹¹)

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

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

2
1
11

2
11