Restoring Numbers

Given a positive integer N, decompose N into prime factors. For each prime factor, output the factor and the number of times it appears in the factorization.

The first line contains the number of test cases T. Each of the next T lines contains one positive integer N. Every N satisfies 2 <= N <= 100,000.

For each test case, output the prime factors of N in increasing order. On each line, print a prime factor and its exponent separated by one space.