Restoring Numbers

Interview

Time limit2sMemory limit128 MB

Summary

For each given integer up to 100,000, output its prime factorization as prime-exponent pairs in increasing order.

Level: Easy2 of 10
Topics: Math, Number theory, Brute force
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples1

Example 1
Input
```
2
6
24
```
Expected output
```
2 1
3 1
2 3
3 1
```