Hide

# Problem FFizz Buzz

Everybody loves easy problems. And no problem is easier than the Fizz Buzz problem. Indeed, F in Finals stands for Fizz Buzz!

Let $F_0$ denote the following string:

F_in_Finals_stands_for_Fizz_Buzz!


We can recursively generate $F_ i$ (for $i \geq 1$) with the following rule:

• $F_ i$ is the string obtained by replacing all characters F in $F_{i-1}$ by $F_0$ simultaneously.

For example, $F_1$ is the following string (without the line breaks):

F_in_Finals_stands_for_Fizz_Buzz!_in_
F_in_Finals_stands_for_Fizz_Buzz!inals_stands_for_
F_in_Finals_stands_for_Fizz_Buzz!izz_Buzz!


And $F_2$ is the following string (without the line breaks):

F_in_Finals_stands_for_Fizz_Buzz!_in_
F_in_Finals_stands_for_Fizz_Buzz!inals_stands_for_
F_in_Finals_stands_for_Fizz_Buzz!izz_Buzz!_in_
F_in_Finals_stands_for_Fizz_Buzz!_in_
F_in_Finals_stands_for_Fizz_Buzz!inals_stands_for_
F_in_Finals_stands_for_Fizz_Buzz!izz_Buzz!inals_stands_for_
F_in_Finals_stands_for_Fizz_Buzz!_in_
F_in_Finals_stands_for_Fizz_Buzz!inals_stands_for_
F_in_Finals_stands_for_Fizz_Buzz!izz_Buzz!izz_Buzz!


You can keep generating $F_ i$ for all non-negative integers $i$. To test whether you understand this operation, you should answer $Q$ questions $(X_ j, Y_ j)$: what is the $X_ j$-th character of $F_{Y_ j}$?

## Input

The first line of input contains one integer $Q$, the number of questions you need to answer ($1 \leq Q \leq 300\, 000$).

The next $Q$ lines of input each contain two integers $X_ j$ and $Y_ j$ ($1 \leq X_ j \leq 10^{18}$; $0 \leq Y_ j \leq 10^{18}$).

## Output

Output a string of length $Q$. The $j$-th character of the string should be the $X_ j$-th character of $F_{Y_ j}$. If there are less than $X_ j$ characters in $F_{Y_ j}$, output the character ? instead.

Sample Input 1 Sample Output 1
10
157 2
71 1
26 2
128 1
417 2
29 0
250 2
63 1
32 0
34 0

Fizz!Buzz?

Hide