Программисты считают, что счастливые числа - это числа, которые не содержат цифр, кроме 1, 2, 4 и 8. Например, по мнению программистов 11, 8, 184, 1248 - счастливые числа, а 147, 13, 808, 555 - нет.

Ваша задача - иногда найти k-ое счастливое число в порядке возрастания, а иногда найти наименьшее счастливое число, большее заданного числа k. Вы должны написать программу, которая правильно отвечает на q запросов этих двух типов.

Входные данные

Первая строка содержит одно целое число q (1 ≤ q ≤ 104) - количество запросов, а каждая из следующих q строк содержит два целых числа ti (ti = {1, 2}) и ki. Если ti = 1, то следует найти ki-ое счастливое число в порядке возрастания, а если ti = 2, то следует найти наименьшее счастливое число, большее ki. Известно, что:

• если ti = 1, то 1 ≤ ki ≤ 2 * 109
• если ti = 2, то 0 ≤ ki ≤ 1015

Выходные данные

Для каждого запроса дайте ответ на этот запрос в новой строке.

Пояснение

Ряд счастливых чисел имеет вид: 1, 2, 4, 8, 11, 12, 14, 18, 21, 22, 24, 28, 41, 42, 44, 48, ... .