Moriarty has challenged Sherlock with a complicated maths problem. Moriarty will provide Sherlock two arrays a and b. Sherlock should multiply all the numbers in a, which will form a large number A. Then Sherlock should multiply all the numbers in b, which will form a large number B. Sherlock needs to find two positive integers p and q, such that q*A=p*B and gcd(p, q) = 1. Since, p and q will also be large numbers, Moriarty wants the value of p modulo 1000000007(1e9 + 7) and q modulo 1000000007(1e9 + 7).

Note:- Here, gcd(a , b) indicates greatest common divisor of a and b. Learn about gcd here.

Learn how to answer modulo 1000000007 here.

Note:- Python has not been allowed for this problem as python provides some features that hides the main motive for this problem. Sorry for the inconvenience.

Note:- Use of fast I/O is recommended.

See the sample case for better understanding.

Input format:

First line contains an integer T, denoting the number of test-cases.

Next 3T lines contain the test-cases as shown below:-

First line contains two integers n and m, representing the sizes of arrays a and b respectively.

Second line contains n space separated integers(a1, a2, ... an). Here, ai indicates ith element of array a.

Third line contains m space separated integers(b1, b2, ... bm). Here, bi indicates ith element of array b.

Output format:

For each testcase, print values of p modulo 1000000007(1e9 + 7) and q modulo 1000000007(1e9 + 7) in a new line.

Constraints:

1 <= T <= 10

1 <= n, m <= 100000

1 <= ai, bi <= 1000000(1e6)

Subtasks:

Subtask #1 (10 points) : n = m = 1

Subtask #2 (10 points) : A, B <= 1e18

Subtask #3 (10 points) : 1 <= n, m <= 100

Subtask #4 (10 points) : 1 <= n, m <= 1000

Subtask #5 (60 points) : Original Constraints