The first number in a sequence of numbers is 1. Every subsequent \((i^{th})\) number of the sequence is constructed by applying the following operations on the \((i-1)^{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 \(j^{th}\) digit of the \(i^{th}\) number in this sequence. If the \(i^{th}\) 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 \(j^{th}\) digit of the \(i^{th}\) number in this sequence. If the \(i^{th}\) number has less than j digits, print -1.

Constraints

\(1 \le T \le 10^4\)
\(1 \le i \le 10^6\)
\(1 \le j \le 10^{12}\)