← 返回题目列表

AtCoder · arc176_b

B. 简单数学 4

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

找到余数的最后一位 2^N 除以 2^M - 2^K.

你被给予 T 测试用例,每个测试用例都必须解决。

约束

  • 1 \le T \le 2 \times 10^5
  • 1 \le N \le 10^{18}
  • 1 \le K < M \le 10^{18}
  • N,M,K 是整数。

输入

输入由标准输入按以下格式给出,其中 \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

示例输出 1

2
8
8
8
4

对于第一个测试用例,剩余的 2^9 除以 2^6 - 2^2 is 32。因此,答案是最后一位数字 32,即 2.