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^9+7.

Example

Input:
1
5 6
Output:
5760