The problem is very simple. given two integers n and m, find the product GCD(1, 1) × GCD(1, 2) × ... × GCD(1, M) × GCD(2, 1) × GCD(2, 2) × ... × GCD(2, M) × ... × GCD(N, 1) × GCD(N, 2) × ... × GCD(N, M).

Input

The first line will be the number of test cases t, followed by t lines, each having two numbers n and m (1 ≤ n, m ≤ 10000000) (1 ≤ t ≤ 5).

Output

Output the required solution modulo 10⁹+7.

Example

Input:
1
5 6

Output:
5760