어려운 소인수분해

지원이는 대회에 낼 문제를 고민하다가 소인수분해 문제를 출제하기로 마음먹었다. 그런데 그 얘기를 들은 동생이 한 말이 지원이의 기분을 상하게 했다.

"소인수분해? 그거 너무 쉬운 거 아니야?"

지원이는 소인수분해가 어렵다는 걸 알려주려고 자신만만한 동생에게 2와 500만 사이의 자연수 N개를 주고 소인수분해를 시켰다. 그러자 동생은 기겁하며 쓰러졌다. 힘들어하는 동생을 대신해서 여러분이 이것도 쉽다는 걸 보여주자!

첫째 줄에는 자연수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다.

둘째 줄에는 자연수 ki (2 ≤ ki ≤ 5,000,000, 1 ≤ i ≤ N)가 N개 주어진다.

N줄에 걸쳐서 자연수 ki의 소인수들을 오름차순으로 출력하라.