Ben had two numbers $$M$$ and $$N$$. He factorized both the numbers, that is, expressed $$M$$ and $$N$$ as a product of prime numbers.
                  M = (P₁^A₁)*(P₂^A₂ )*(P₃^A₃)*… *(P_N^A_N)
                  N = (Q₁^B₁)*(Q₂^B₂ )*(Q₃^B₃)*… *(Q_N^B_N)

• Here, * represents multiplication.
• P₁, P₂ ...P_N  are distinct prime numbers. 
• Q₁, Q₂ ...Q_N are distinct prime numbers.

Unfortunately, Ben has lost both the numbers $$M$$ and $$N$$ but still he has arrays $$A$$ and $$B$$. He wants to reterive the numbers $$M$$ and $$N$$ but he will not be able to. Your task is to determine the minimum and the maximum number of factors their product (that is, $$M*N$$) could have. Your task is to tell Ben the minimum and the maximum number of factors that the product of $$M$$ and $$N$$ could have.
Since the answer can be large, print modulo $$1000000007$$.

Input format

• The first line contains an integer $$T$$ denoting the number of test cases. For each test case:
  • The first line contains an integer $$N$$ denoting the number of elements in arrays $$A$$ and $$B$$.
  • The second line contains $$N$$ space-separated integers of array $$A$$.
  • The third line contains $$N$$ space-separated integers of array $$B$$.

Output format

For each test case, print a single line line containing two integers denoting the minimum and maximum number of factors which a product of $$M$$ and $$N$$ could have.

Constraints

\(1 \leq T \leq 20000\)

\(1 \leq N \leq 200000\)

\(1 \leq A_i ,B_i \leq 10^6\)

The sum of $$N$$ over all test cases does not exceed 200000.