This problem tests your mathematic knowledge and your programming ability very much. Your task is to calculate the number of different Minimum Spanning Trees (MSTs) of a special undirected unweighted graph. The graph has n nodes numbered from 1 to n, and there is an edge between node i (1 ≤ i ≤ n) and node j (1 ≤ j ≤ n) if and only if 0 < |i-j| ≤ k.

Input

Multiple test cases, the number of them (≤ 8) is given in the very first line.

Each test case contains one line with two space-separated numbers k (1 ≤ k ≤ 5) and n (1 ≤ n ≤ 10¹⁵).

Output

For each test case you should output one line, the number of different MSTs of the corresponding graph modulo 65521.

Example

Input:
1
3 5

Output:
75