Background

Special for beginners, ^_^

Description

求 $2^N$ 除以 $2^M-2^K$ 的余数的最低位。

Format

Input

第一行一个正整数 $T（\le2\times10^5）$ 表示数据组数。

接下来 $T$ 行，每行一组数据，包含三个不超过 $10^{18}$ 的正整数，$N$ 、 $M$ 和 $K（K<M）$ 。

Output

每行输出一个答案。

Samples

1
8 5 1

6

Limitation

1s, 1024KiB for each test case.