该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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.