문제가 있는 공개 키

2012년 2월 15일, 뉴욕 타임스는 공개 키 암호 체계의 키 생성 방식에 결함이 있다고 보도했다(John Markoff의 기사 "Researchers Find a Flaw in a Widely Used Online Encryption Method"). 이 결함을 이용하면 공격자가 결함 있는 공개 키 집합으로부터 개인 키를 알아낼 수 있다.

여러분은 결함 있는 공개 키를 입력받아 그에 대응하는 개인 키를 구하는 프로그램을 작성해야 한다. 이 문제에서 개인 키는 두 소수의 쌍

$2 < K_1, K_2 < 2^{31}$

이고, 대응하는 공개 키는 곱 $K_1 \times K_2$이다.

입력의 첫째 줄에는 정수 $M$ ($2 \le M \le 100$)이 주어진다. $M$은 이어지는 입력 줄의 수이다. 다음 $M$개 줄에는 각각 공개 키 하나가 주어진다. 각 공개 키는 정확히 두 소수의 곱이며 32비트 부호 없는 정수에 들어간다.

프로그램은 입력 값들의 소인수를 중복 없이 오름차순으로 출력해야 하며, 마지막 줄을 제외하고 한 줄에 다섯 개씩 출력한다. 같은 줄의 값들은 공백 하나로 구분한다.