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.