Sequence of numbers

0

0 votes
Recursion, Hard, Memoization, Recruit, Algorithms, Grammar-Verified, Approved, Dynamic programming
Problem

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 (i1)th number:

  • Replacing 1 with 114
  • Replacing 4 with 1

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

  • First line: T (number of test cases)
  • First line in each test case: Two space-separated integers i and j

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

1T104
1i106
1j1012

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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.

Editor Image

?