Щасливі числа

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

Ваше завдання - іноді визначити $k$-те щасливе число в порядку зростання, а іноді знайти найменше щасливе число, яке більше за задане число $k$. Ви повинні написати програму, яка правильно відповідає на $q$ запитів цих двох типів.

Вхідні дані

Перший рядок містить одне ціле число $q$ $(1\le q\le 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\le k_i\le 2\ast 10^9$

• якщо $t_i$ = $2$, то $0\le k_i\le 10^{15}$

Вихідні дані

Для кожного запиту виведіть відповідь у новому рядку.

Приклади

Примітка

Послідовність щасливих чисел виглядає так: $1$, $2$, $4$, $8$, $11$, $12$, $14$, $18$, $21$, $22$, $24$, $28$, $41$, $42$, $44$, $48$, ... .