Solve the programming task below in a Python markdown code block.
When you look at photographs of watches and clocks, you'll find that they almost always show the time 10:10. There are lots of theories and even urban legends about this. For example, when showing 10:10, the hands look like a smile, and so you are more inclined to buy the watch or clock :D (a form of subliminal advertising).

Now, you are given $N$ and ${M}$. You are to find the number of sequences $A_{1},A_{2},\ldots,A_{N}$ such that:

${A_1}$ is a number of the form ${1010}^K$ for some $1\leq K\leq M$,
If $P=A_2\cdot A_3\cdots A_N$, then ${A_1}$ is divisible by ${P}$, and $\mbox{P}$ is divisible by ${1010}$, and
$A_2,A_3,\ldots,A_N$ are squarefree.

Since the number can be very large, only give the number modulo ${2000003}$.

Input Format 

The first line of input contains a single integer ${T}$, which is the number of test cases. The following lines contain the test cases.

Each test case consists of one line containing two integers, $N$ and ${M}$.

Constraints 

$1\leq T\leq10^5$ 

$2\leq N\leq M\leq10^{12}$  

Output Format 

For each test case, output a single line containing the answer.

Sample Input  

2
2 3
3 3

Sample Output  

3
62

Explanation 

For the first test case, the possible sequences are: 

$\{1010,1010\}$, 

$\{1020100,1010\}$, 

${103031000},{1010}$