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