Competitions

# Lucky numbers

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 (1q104) - 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 1ki2 * 109,
• if ti = 2 then 0ki1015.

#### 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, ... .

Time limit 1 second
Memory limit 128 MiB
Input example #1
4
1 7
2 18
2 25
2 0

Output example #1
14
21
28
1

Source 2023 Azerbaijan, Semifinals, February 18, 8 - 9 classes