Given the positive integers N = p₁ * p₂ * ... * p_k and M = (p₁ - 1) * (p₂ - 1) * ... * (p_k - 1), i.e. M = φ(N) (Euler's totient function), where k ≥ 1, p_i ≠ p_j for all i ≠ j with i, j = 1, 2 ... k and p_i is prime number for all i = 1, 2 ... k, your task is factor n.

Input

The first line contains a positive integer T, the number of test cases, where T ≤ 100. The following T lines each contains two numbers N and M in this order, where N < 10¹⁰⁰.

Output

Output T lines, with prime factorization of N according with example.

Example

Input:
3
210 48
983 982
14351 14112

Output:
210 = 2 * 3 * 5 * 7
983 = 983
14351 = 113 * 127