Description:

Once upon a time there was a man who had multiple girlfriends. Each girl thought she was the only one in the man's heart but this was not true. He was cheating on all of them.

N houses were situated in a row and each house had exactly one of his girlfriends living there.

One day he wanted to visit K of his girlfriends but he then realized that he couldn't visit two consecutive houses. That would be too dangerous.

How many different ways did the man have for visiting his girlfriends?

The ordering of houses does not matter. i.e, how many different combinations of houses could the man consider.

Input Format

The first line contains an integer T - the number of test cases. Next follow T lines, each containing two space separated integers, N and K.

Constraints

1 <= T <= 10  
1 <= N <= 10^15   
1 <= K <= 10^15    

Output format

The output must contain T lines, each containing one integer - the number of ways the man can visit his girlfriends. Output the answer modulo 100003.

Sample input

4
7 3
8 5
10 5
100000 555

Sample output

10
0
6
14258

Hint

For example, in the first test case, there are 7 houses, and the lover will visit 3 of them without visiting two in consecutive positions. The 10 ways are these:

X0X0X00
X0X00X0
X0X000X
X00X0X0
X00X00X
X000X0X
0X0X0X0
0X0X00X
0X00X0X
00X0X0X
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score