The first number in a sequence of numbers is 1. Every subsequent (ith) number of the sequence is constructed by applying the following operations on the (i−1)th number:
Therefore, the sequence will be as follows:
1, 114, 1141141, 11411411141141114 , ...
Write a program to find a digit which is the jth digit of the ith number in this sequence. If the ith number has less than j digits, print -1.
Input format
Output format
For each test case, print a digit which is the jth digit of the ith number in this sequence. If the ith number has less than j digits, print -1.
Constraints
1≤T≤104
1≤i≤106
1≤j≤1012
1st test case: 2nd number in the sequence is 114, 2nd digit is 1.
2nd test case: 2nd number in the sequence is 114, 3rd digit is 4.