Hard Prime Factorization

Interview

Time limit2sMemory limit512 MB

Summary
Factor each of up to one million numbers up to 5,000,000 and print its prime factors in increasing order.
Level

Medium4 of 10

Topics
Number theory, Array, Math, Implementation
Solved
No attempts yet

Problem

Jiwon was thinking about problems for a contest and decided to set a prime factorization problem. His younger sibling's reaction to the news ruined his mood.

"Prime factorization? Isn't that way too easy?"

To show how hard prime factorization can be, Jiwon gave his overconfident sibling N natural numbers between 2 and 5 million and told the sibling to factorize them. The sibling was so shocked that they collapsed. Stand in for the struggling sibling and show that this is easy too!

Input

The first line gives the number of natural numbers N (1 ≤ N ≤ 1,000,000).

The second line gives N natural numbers ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N).

Output

Over N lines, output the prime factors of each natural number ki in increasing order.

Examples1

  1. Example 1

    Input
    5
5 4 45 64 54
    Expected output
    5
2 2
3 3 5
2 2 2 2 2 2
2 3 3 3