Description

The binomial coefficient $C_n^{k}$ is the number of ways of picking $k$ unordered outcomes from $n$ possibilities, also known as a combination or combinatorial number.

Give $n$ and $k$, you are required to calculate $C_n^{k}$ mod 10000003.

Format

Input

The input contains several test cases. The first line of the input contains one positive integer, $c$, denoting the number of test cases.

Each of the following $c$ lines contains two integers, $n(0\le n\le 1000)$ and $k (0\le k\le n)$, denoting that you are required to calculate $C_n^k$ mod 10000003.

Output

For each test case, output one line containing $C_n^k$ mod 10000003.

Samples

3
1 1
10 2
954 723

1
45
3557658