Fun Count Not Fun#12383
You are given two integers and . An initial array is constructed as [1, 2, 3, \dots, n].
While the length of the array is at least , you perform the following process:
Select any contiguous subarray of length exactly .
Delete this subarray from .
Concatenate the remaining left and right parts to form a new array .
The process terminates when |A| < k.
Determine the number of distinct arrays that can exist when the process stops. Since the count can be large, output the result modulo .
The first line contains an integer (1 \le T \le 10^6) — the number of test cases.
Each of the following lines contains two space-separated integers and (1 \le n, k \le 10^6).
For each test case, output a single integer representing the number of distinct terminal arrays modulo .
Example 1
Subtask ( points): 1 \le n, k \le 10.
Subtask ( points): \sum n \cdot k \le 10^6 over all test cases.
Subtask ( points): \sum n \le 10^6 over all test cases.
Subtask ( points): is the same across all test cases.
Subtask ( points): No additional constraints.