시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 52 34 30 68.182%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

5
7
12
64
72
1337

예제 출력 1

7
3 4
4 16
2 4 9
7 191
W3sicHJvYmxlbV9pZCI6IjkzMjYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJNSTYiLCJkZXNjcmlwdGlvbiI6IjxwPk1JNlx1YjI5NCBcdWMyYTRcdWQzMGNcdWM3NzRcdWM3NTggXHVjMmUwXHVjNmQwXHVjNzQ0IFx1ZDY1NVx1Yzc3OFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVjMmE0XHVkMzBjXHVjNzc0IFx1YzJkZFx1YmNjNCBcdWNmNTRcdWI0ZGMoU3B5IElkZW50aVx1ZmIwMWNhdGlvbiBDb2RlLCBTSUMpXHViOTdjIFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgXHVjODFjXHVjNzg0XHVjMmE0IFx1YmNmOFx1YjRkY1x1Yzc1OCBTSUNcdWIyOTQgN1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+TUk2XHViMjk0IFx1YzJhNFx1ZDMwY1x1Yzc3NFx1Yzc1OCBcdWFkZjhcdWI4ZjlcdWFjZmMgXHVhZGY4XHViOGY5XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWMyYTRcdWQzMGNcdWM3NzRcdWI5N2MgXHVjMjdkXHVhYzhjIFx1YzU0Y1x1YzU0NFx1YmNmYyBcdWMyMTggXHVjNzg4XHVhYzhjIFx1ZDU1OFx1YWUzMCBcdWM3MDRcdWQ1NzQgU0lDXHViOTdjIFx1ZDU2MFx1YjJmOVx1ZDU1Y1x1YjJlNC4gXHVhZGY4XHViOGY5XHVjNzQwIFx1YzBjMVx1ZDBkYyBcdWNmNTRcdWI0ZGNcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWIzNzAsIFx1YzBjMVx1ZDBkYyBcdWNmNTRcdWI0ZGNcdWIyOTQgXHVhZGY4XHViOGY5XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjMmE0XHVkMzBjXHVjNzc0XHVjNzU4IFNJQ1x1Yjk3YyBcdWFjZjFcdWQ1NWMgXHVhYzEyXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWQwZGNcdWNmNTRcdWI0ZGNcdWM3NTggXHVkNmE4XHVjNzI4XHVjMTMxXHVjNzQ0IFx1YzcwNFx1ZDU3NCwgMlx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YmFhOFx1YjRlMCBcdWMwYzFcdWQwZGNcdWNmNTRcdWI0ZGNcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWFjMDEgXHVjMGMxXHVkMGRjXHVjZjU0XHViNGRjXHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWMyYTRcdWQzMGNcdWM3NzQgXHVhZGY4XHViOGY5XHVjNzc0IFx1YzcyMFx1Yzc3Y1x1ZDU1OFx1YWM4YyBcdWM4NzRcdWM3YWNcdWQ1NThcdWFjZTAsIFx1YWMwMSBcdWMyYTRcdWQzMGNcdWM3NzQgXHVhZGY4XHViOGY5XHVjMGFjXHVjNzc0XHVjNzU4IFx1YzBjMVx1ZDBkY1x1Y2Y1NFx1YjRkYyBcdWFjMTJcdWM3NzQgXHViMmU0XHViOTc0XHVhYzhjIFx1YjQxOFx1YjNjNFx1Yjg1ZCBTSUNcdWI5N2MgXHViYzMwXHVjODE1XHVkNTU4XHViODI0IFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVkMGRjIFx1Y2Y1NFx1YjRkY1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFkZjggXHVhZGY4XHViOGY5XHVjNWQwIFx1YzE4ZFx1ZDU1OFx1YjI5NCBcdWMyYTRcdWQzMGNcdWM3NzRcdWM3NTggU0lDXHViOTdjIFx1YmFhOFx1YjQ1MCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCAxMDBcdWFjMWNcdWI5N2MgXHViMTE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWQwZGMgXHVjZjU0XHViNGRjIGMmbmJzcDsoMiAmbGU7IGMgJmxlOyAxMDxzdXA+OTxcL3N1cD4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNCBcdWI5YzhcdWIyZTQsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjMGMxXHVkMGRjIFx1Y2Y1NFx1YjRkY1x1YzVkMCBcdWMxOGRcdWQ1NThcdWIyOTQgXHVjMmE0XHVkMzBjXHVjNzc0XHVjNzU4IFNJQ1x1Yjk3YyBcdWM2MjRcdWI5ODRcdWNjMjhcdWMyMWNcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBTSUMgXHVjMGFjXHVjNzc0XHVjNWQwXHViMjk0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWQ1NThcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjkzMjYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJJZGVudGlmaWNhdGlvbiBDb2RlIiwiZGVzY3JpcHRpb24iOiI8cD5NSTYgdXNlcyBhIFNweSBJZGVudGlcdWZiMDFjYXRpb24gQ29kZSAoU0lDKSB0byBpZGVudGlmeSB0aGVpciBzcGllcy4gRm9yIGV4YW1wbGUsIEouIEIuJm5ic3A7aGFzIGEgU0lDIG9mIDcuIFRoZSBTSUNzIGhhdmUgYmVlbiBhc3NpZ25lZCB0byB0aGUgc3BpZXMgaW4gc3VjaCBhIHdheSB0aGF0IE1JNiBjYW4gZWFzaWx5IHJlZmVyIHRvIGFueSBncm91cCBvZiBzcGllcyBieSB1c2luZyBhIHN0YXR1cyBjb2RlIHRoYXQgaXMgdGhlIHByb2R1Y3Qgb2YgYWxsIFNJQ3Mgb2YgdGhlIHNwaWVzIGluIHRoZSBncm91cC4gTW9yZSBwcmVjaXNlbHksIHRoZSBTSUNzIGFyZSBjaG9zZW4gaW4gc3VjaCBhIHdheSB0aGF0IGVhY2ggc3RhdHVzIGNvZGUgJmdlOyAyIHJlZmVycyB0byBhIHVuaXF1ZSBncm91cCBvZiBzcGllcywgYW5kIGZvciBlYWNoIGdyb3VwIG9mIHNwaWVzIHRoZXJlIGlzIGEgdW5pcXVlIHN0YXR1cyBjb2RlIHJlZmVycmluZyB0byBpdC48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQsIGdpdmVuIGEgc3RhdHVzIGNvZGUsIHJldHVybnMgdGhlIFNJQ3Mgb2YgdGhlIHNwaWVzIHRoYXQgYmVsb25nIHRvIHRoZSBncm91cCBjb3JyZXNwb25kaW5nIHRvIHRoYXQgc3RhdHVzIGNvZGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBjICgyICZsZTsgYyAmbGU7IDEwPHN1cD45PFwvc3VwPik6IHRoZSBzdGF0dXMgY29kZS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCBhIHNwYWNlLXNlcGFyYXRlZCBsaXN0IG9mIFNJQ3MgZm9yIHRoZSBzdGF0dXMgY29kZSwgaW4gaW5jcmVhc2luZyBvcmRlcjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d