题目描述

给定 $2^N$，请你求出它除以 $2^M - 2^K$ 的余数的个位数字。

有 $T$ 组测试数据，请分别输出每组的答案。

输入格式

输入以如下格式从标准输入读入。其中，$\mathrm{case}_i$ 表示第 $i$ 个测试用例。

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

每组测试数据格式如下：

$N$ $M$ $K$

输出格式

请输出答案。

样例 1

输入

5
9 6 2
123 84 50
95 127 79
1000000007 998244353 924844033
473234053352300580 254411431220543632 62658522328486675

输出

2
8
8
8
4

说明/提示

限制条件

• $1 \leq T \leq 2 \times 10^5$
• $1 \leq N \leq 10^{18}$
• $1 \leq K < M \leq 10^{18}$
• $N, M, K$ 均为整数

样例解释 1

对于第 $1$ 个测试用例，$2^9$ 除以 $2^6 - 2^2$ 的余数是 $32$。因此 $32$ 的个位数字 $2$ 就是答案。

由 ChatGPT 4.1 翻译