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.
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
.
For each query, print the answer on a new line.
A series of lucky numbers looks like: 1, 2, 4, 8, 11, 12, 14, 18, 21, 22, 24, 28, 41, 42, 44, 48, ... .