MI6는 스파이의 신원을 확인하기 위해서 스파이 식별 코드(Spy Identification Code, SIC)를 사용한다. 예를 들어, 제임스 본드의 SIC는 7이다.

MI6는 스파이의 그룹과 그룹에 속하는 스파이를 쉽게 알아볼 수 있게 하기 위해 SIC를 할당한다. 그룹은 상태 코드로 나타낼 수 있는데, 상태 코드는 그룹에 속하는 모든 스파이의 SIC를 곱한 값이다.

상태코드의 효율성을 위해, 2보다 크거나 같은 모든 상태코드에 대해서, 각 상태코드를 가지는 스파이 그룹이 유일하게 존재하고, 각 스파이 그룹사이의 상태코드 값이 다르게 되도록 SIC를 배정하려 한다.

상태 코드가 주어졌을 때, 그 그룹에 속하는 스파이의 SIC를 모두 구하는 프로그램을 작성하시오.

입력 형식

첫째 줄에 테스트 케이스의 수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다. 각 테스트 케이스의 첫째 줄에는 상태 코드 c (2 ≤ c ≤ 10⁹)가 주어진다.

출력 형식

각 테스트 케이스 마다, 입력으로 주어진 상태 코드에 속하는 스파이의 SIC를 오름차순으로 출력한다. SIC 사이에는 공백을 하나 출력한다.

예제 입력

5
7
12
64
72
1337

예제 출력

7
3 4
4 16
2 4 9
7 191