Problem Statement

Find the last digit of the remainder when $2^N$ is divided by $2^M - 2^K$.

You are given $T$ test cases, each of which must be solved.

Constraints

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 10^{18}$
• $1 \le K < M \le 10^{18}$
• $N,M,K$ are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{case}_i$ represents the $i$-th test case:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each test case is given in the following format:

N M K

Output

Print the answer.