Bheem and his friends were playing with numbers in the jungle but suddenly there came a storm, all the trees started displacing from their places, animals running here and there to survive the storm. Yes it was Kirmada back again to conquer Dholakpur, the only kingdom left in the world that was not conquered by him. He challenged Bheem again to save Dholakpur as this time Kirmada was even stronger than earlier, but this time the challenge was not to fight against him to save Dholakpur but the challenge was with numbers.
With his magical power Kirmada concatenated all the number from 1 to N and gave Bheem a number k and challenged him to tell the digit at k^th index in the concatenated number. Help Bheem win this challenge and save Dholakpur.

 

Input

• The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.

 

• Next T contains 2 space-separated integers N and k

 

Output

• For each test case, output a single line containing the k^th digit (1-based indexing) in the concatenated number.

 

Constraints

• 1 = T = 100000
• 1 = N = 10^15
• 1 = k = the length of concatenated number

 

Example

Input: 2 10 5 15 16 Output: 5 1

 

Explanation

Example case 1. concatenating all numbers from 1 to 10 gives 1234567810 and the 5th digit in the concatenated number is 5.
Example case 2. concatenating all numbers from 1 to 15 gives 123456789101112131415 and the 16th digit in the concatenated number is 1.

Note: The problem originally belongs to one of the Google Interview Questions.