B - Simple Math 4 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

2^N を 2^M - 2^K で割ったあまりの 1 の位を求めてください。

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

1 個目のテストケースについて、2^9 を 2^6 - 2^2 で割ったあまりは 32 です。よって 32 の 1 の位の 2 が答えです。

Score : 400 points

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.

Sample Input 1

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

Sample Output 1

2
8
8
8
4

For the first test case, the remainder of 2^9 divided by 2^6 - 2^2 is 32. Thus, the answer is the last digit of 32, which is 2.