Cerebro was a machine designed by Professor Charles Xavier to locate mutants with the X-Gene, and it was located in Xavier’s mansion on the second sub-basement under heavy security.

Bastion assembled the international anti-mutant strike force and launched Operation: Zero Tolerance, in order to confiscate Cerebro. He has managed to reach the basement, but has to enter a K digit passcode to proceed further. However, the passcode isn’t so simple. The i^th digit of the passcode is the value of the K_i^th digit of the Xavier constant. The Xavier constant is defined by concatenating representations of successive integers.

Xavier constant = 123456789101112131415161718.....

Bastion was able to fnd the answer for very small values of K_i, but needs your help to calculate the answer for extremely large values of K_i. You will be given K queries in the form of space separated integers. For each query you have to fnd the value of the K_i^th digit of the Xavier constant and output the K- digit passcode in a single line.

INPUT
First line of input contains an positive integer T – denoting the number of test cases. The fIrst line of each test case contains an integer K- denoting the number of queries. The second line of test case contains K space-separated integers where K_i denotes the digit whose value in the Xavier constant is to be calculated.

CONSTRAINTS
1 <= T <= 100
1 <= K <= 15
Subtask 1: 20 points
  1 <= K_i <= 10⁶
Subtask 2: 80 points
  1 <= K_i <= 10¹⁵

OUTPUT
For each test case, in a single line print the correct K-digit passcode (without spaces).