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

Вхідні дані

Перший рядок містить одне ціле число $q$ $(1 \leq q \leq 1 0^{4})$ (1 ≤ q ≤ 10^4) - кількість запитів. Кожен з наступних $q$ рядків містить два цілі числа $t_{i}$ t_i $(t_{i} = 1, 2)$ (t_i = {1, 2}) та $k_{i}$ k_i. Якщо $t_{i} = 1$ t_i = 1, потрібно знайти $k_{i}$ k_i-те щасливе число в порядку зростання, а якщо $t_{i} = 2$ t_i = 2, потрібно знайти найменше щасливе число, більше за $k_{i}$ k_i. Відомо, що:

якщо $t_{i}$ t_i = $1$ , то $1 \leq k_{i} \leq 2 * 1 0^{9}$ 1 ≤ k_i ≤ 2 * 10^9
якщо $t_{i}$ t_i = $2$ , то $0 \leq k_{i} \leq 1 0^{15}$ 0 ≤ k_i ≤ 10^{15}

Вихідні дані

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

Приклади

Приклад 1

Loading

Примітка

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