Read problems statements [Hindi] ,[Bengali] , [Mandarin chinese] , [Russian] and [Vietnamese] as well.

The Euler totient function $\varphi(N)$ is defined as the number of integers between $1$ and $N$ (inclusive) which are coprime with $N$.

You are given $N$ and $\varphi(N)$. Calculate the prime factorization of $N$.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains two space-separated integers $N$ and $\varphi(N)$.

------ Output ------
For each test case, print a line containing a single integer $K$ — the number of distinct prime factors of $N$. Then, print $K$ lines. For each valid $i$, the $i$-th of these lines should contain two space-separated integers $p_{i}$ and $e_{i}$ denoting a prime divisor of $N$ and its exponent. Specifically, the following conditions should hold:
$N = \prod_{i=1}^{K} p_{i}^{e_{i}}$
$p_{i} < p_{i+1}$ for each valid $i$
$e_{i} > 0$ for each valid $i$

------ Constraints ------
$1 ≤ T ≤ 10$
$2 ≤ N ≤ 10^{500}$

------ Subtasks ------
Subtask #1 (5 points): $2 ≤ N ≤ 10^{14}$

Subtask #2 (25 points): $2 ≤ N ≤ 10^{50}$

Subtask #3 (70 points): $2 ≤ N ≤ 10^{500}$

----- Sample Input 1 ------
2

6 2

8 4
----- Sample Output 1 ------
2

2 1

3 1

1

2 3

见题面

见题面