You have to design a new model which maps an even length palindromic number to some digit between 0 to 9.
The number is mapped to a digit \(x\) on the basis of following criteria:
1. \(x\) should appear maximum number of times in the palindromic number, that is, among all digits in the number, \(x\) should appear maximum number of times.
2. If more than one digit appears maximum number of times, \(x\) should be the smallest digit among them.

Given an integer \(N\), you have to find the digit \(x\) for the \(N^{th}\) even length palindromic number.

Note- First 9 even length palindromic numbers are:

            11, 22, 33, 44, 55, 66, 77, 88, 99

Input :

    First line contains T, number of test cases.

    Each of the next T lines contains an integer N.

Output:

    For each test case, print the digit to which the \(N^{th}\) even length palindromic number is mapped.
    Answer for each test case should come in a new line.

Constraints:

    \(1 \le T \le 10^5\)

    \(1 \le N \le 10^{18}\)