SP5911 SQFFACT - Square-free Integers Factorization

Given the positive integers N = p $ _{1} $ \* p $ _{2} $ \* ... \* p $ _{k} $ and M = (p $ _{1} $ -1) \* (p $ _{2} $ -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.

The first line contains a positive integer T, the number of test cases, where T

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