Lucky numbers — Eolymp

Input

The first line contains one integer $q$ $(1 \leq q \leq 1 0^{4})$ (1 ≤ q ≤ 10^4) - the number of queries, and each of the following $q$ lines contains two integers $t_{i}$ t_i $(t_{i} = 1, 2)$ (t_i = {1, 2}) and $k_{i}$ k_i. If $t_{i} = 1$ t_i = 1 then find the $k_{i}$ k_i-th lucky number in ascending order, and if $t_{i} = 2$ t_i = 2 then find the smallest lucky number greater than $k_{i}$ k_i. It is known that:

if $t_{i}$ t_i = $1$ then $1 \leq k_{i} \leq 2 * 1 0^{9}$ 1 ≤ k_i ≤ 2 * 10^9,
if $t_{i}$ t_i = $2$ then $0 \leq k_{i} \leq 1 0^{15}$ 0 ≤ k_i ≤ 10^{15}.

Output

For each query, print the answer on a new line.

Examples

Example 1

Loading

Note

A series of lucky numbers looks like: $1$ , $2$ , $4$ , $8$ , $11$ , $12$ , $14$ , $18$ , $21$ , $22$ , $24$ , $28$ , $41$ , $42$ , $44$ , $48$ , ... .