Given two integers $n$ and $\textbf{r}$. In how many ways can $\textbf{r}$ items be chosen from $n$ items?

Input Format

The first line contains the number of test cases $\mathbf{T}$. Each of the next $\mathbf{T}$ lines contains two integers $n$ and $\textbf{r}$.

Constraints

$1\leq T\leq10^5$

$1\leq n\leq10^9$

$0\leq r\leq n$

Output Format

Output $\mathbf{T}$ lines, containing the required answer for the corresponding test case. Output all answers modulo $142857$.

Sample Input
4
2 1
4 0
5 2
10 3

Sample Output
2
1
10
120

见题面

见题面