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 ≤ 104) - the number of queries, and each of the following q lines contains two integers ti (ti = {1, 2}) and ki. If ti = 1 then find the ki-th lucky number in ascending order, and if ti = 2 then find the smallest lucky number greater than ki. It is known that:

• if ti = 1 then 1 ≤ ki ≤ 2 * 109,
• if ti = 2 then 0 ≤ ki ≤ 1015.

Output

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

Explanation

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