Lucky numbers

Very hard

Execution time limit is 1 second

Runtime memory usage limit is 128 megabytes

Programmers consider lucky numbers to be the numbers that contain no digits other than 1, 2, 4 and 8. For example, according to programmers, 11, 8, 184, 1248 are lucky numbers, and 147, 13, 808 , 555 are not.

Your task is sometimes to find the k-th lucky number in ascending order, and sometimes to find the smallest lucky number greater than the given number k. Write a program that correctly answers q of these two types of queries.

Input

The first line contains one integer q (1 ≤ q ≤ 10^4) - the number of queries, and each of the following q lines contains two integers t[i] (t[i] = {1, 2}) and k[i]. If t[i] = 1 then find the k[i]-th lucky number in ascending order, and if t[i] = 2 then find the smallest lucky number greater than k[i]. It is known that:

if t[i] = 1 then 1 ≤ k[i] ≤ 2 * 10^9,
if t[i] = 2 then 0 ≤ k[i] ≤ 10^15.

Output

For each query, print the answer on a new line.

Examples

Input #1

Answer #1

Note

A series of lucky numbers looks like: 1, 2, 4, 8, 11, 12, 14, 18, 21, 22, 24, 28, 41, 42, 44, 48, ... .

Submissions 777

Acceptance rate 20%