Given $n$ and $k$, find the value of $\min\{\frac{n!}{k! (n - k)!}, 10^{18}\}$.

Here, $n! = 1 \times 2 \times \dots \times n$ denotes the factorial of $n$.

Input

The input contains multiple test cases. Process until the end of the file.

Each test case contains two integers $n$ and $k$.

• $0 \leq k \leq n \leq 10^9$
• At most $10^5$ test cases.

Output

For each test case, output an integer representing the required value.

Examples

Input 1

1000000000 0
1000000000 2
1000000000 500000000

Output 1

1
499999999500000000
1000000000000000000