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:
f(a)_i = a_i + a_{i+1} + \ldots + a_{i+k-2} + a_{i+k-1} (here we assume that a_{n + i} = a_i, i.e. numbers are arranged in a circle).
For example, for n = 4, k = 2, f([0, 1, 1, 0]) = [1, 2, 1, 0].
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.
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).
For each test case print the number of different arrays among , modulo .
Example 1
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].