Jigya is in love with pokemons and her favourite one is Jiglypuff. Jigglypuff uses its eyes to mesmerise opponents. Once it achieves this, it will inflate its lungs and begin to sing a soothing lullaby. She took it to a museum. People are standing outside the museum in a line in ascending order as 1,2,3,4,5...

However, our dear Jiglypuff sang a really odd song this time and put really odd people to sleep. More formally, people with odd numbers slept. Now the ticket seller went to every person awake in the line and asked them to write their number on a paper continuously without space.

Hence the initial few characters are 246810121416.....

Now, you want to find the character at ith position on the paper to apologise to the authorities.

Input

First line contains t, number of test cases<=10^3

Each line contains i<=10^5

Output

Character at position i in new line for each test case

Question Setter : Akshay Miterani