Kaosar and GCD#12273
Sign in

Kaosar and GCD

2 seconds
512 megabytes
Hard

You are given two integers and . You have to calculate

\gcd\left( \binom{n}{1}, \binom{n}{2}, \binom{n}{3}, \ldots, \binom{n}{m} \right)

Input

The first line contains a single integer (1 \leq t \leq 10^4).

Each of the next lines contains two integers (1 \leq n \leq 10^9) and (1 \leq m \leq n).

Output

For each test case, output the value of the expression.

Examples

Example 1

Loading
Loading

Scoring

  1. Subtask 1 ( points): 1 \leq m \leq n \leq 2000.

  2. Subtask 2 ( points): No additional constraints.