Счастливые числа

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

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

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

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

• если t[i] = 1, то 1 ≤ k[i] ≤ 2 * 10^9

• если t[i] = 2, то 0 ≤ k[i] ≤ 10^15

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

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

Примеры

Примечание

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