In this problem you have to calculate the determinant of an N x N matrix whose entries are given by m[i][j] = gcd(i,j)^k, 1 ≤ i,j ≤ N.

Here gcd(i,j) denotes the greatest common divisor of i and j.

As the determinant D can grow very large, you have to print D%1000003.

Input

First line of input consists of a single integer containing the number of test cases T ( equal to around 20), each of the following T lines contain two integers N and k where N is the size of the matrix and k is the exponent.
1 ≤ N ≤ 1000000
1 ≤ k ≤ 10⁹

Output

One line corresponding to each test case containing the determinant modulo 1000003 for the corresponding test case.

Example

Input:
3
4 2
2 4
4 3


Output:
288
15
10192