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}$

见题面

见题面