**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.

Submit: 1407 Solved: 198

[Submit][Status][Web Board]

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.

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^{11})

Notice that: the maximum value of a signed 32-bit integer is 2147483647

'long long' in C++, 'long' in Java is recommended.

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
```

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