Cyclic Segment Sums#12885

Cyclic Segment Sums

1 second
256 megabytes
Hard

You are given two integers (2 \le k < n).

For an array a_1, a_2, \ldots, a_n, which consists only of zeros and ones, we define the array as follows:

Consider all 2^n possible arrays , and for each of them, find . How many different arrays are there among them? Since the answer may be very large, print the number of these arrays modulo .

Two arrays are considered different if they differ in at least one position.

Input

The first line contains a single integer (1 \le t \le 10^5)  — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers (2 \le k < n \le 10^6).

Output

For each test case print the number of different arrays among , modulo .

Examples

Example 1

Loading
Loading

Note

For n = 3, k = 2, there are different arrays of ones and zeros. The corresponding arrays are pairwise distinct for them.

For n = 4, k = 2, there are distinct arrays of ones and zeros. The only pair of matching arrays is [0, 1, 0, 1] and [1, 0, 1, 0]: for both arrays is [1, 1, 1, 1].