시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 74 36 22 75.862%

문제

피보나치 수열의 매력에 빠진 현욱이는 피보나치 수열을 너무나도 사랑한 나머지 '피보나치 문제해결전략' 책을 사서 읽다가 Gabonacci 수열의 존재에 대해 알게 된다.

당연히 피보나치 수열에 대해서 알고 있을 것이다. 만약 모른다면  2747번 문제를 풀어 보는 것을 권장한다. n번째 피보나치 항을 Fn이라 할 때 F1 = 1, F2 = 2이며, 그 이후의 항들은 모두 바로 전 2개 항의 합이다. 이러한 귀납적 정의에 따라 피보나치 수열은 1, 1, 2, 3, 5, 8, 13, . . .. 으로 이어진다.

이제 이를 좀 더 일반화해 보자. 어떤 수열이 피보나치 수열과 같은 재귀적 정의  

    G i = Gi-1 + Gi-2 for i > 2

를 따르지만, 처음 두 항을 G 1 ≤ G2 를 만족하게 하면서 임의로 설정할 것이다. 이를 Gabonacci 수열이라고 한다. 만약 G1 = 1, G2 = 3이면, 널리 알려진 수열인 Lucas numbers(1, 3, 4, 7, 11, 18, 29, . . ..)를 얻을 수 있다.

적절한 두 개의 첫 항을 골라서, 당신이 원하는 어떤 자연수를 반드시 Gabonacci 수열에서 등장하게 할 수 있다. 예를 들면, n은 1, n-1로 시작하는 Gabonacci 수열에서 등장한다. 그러나 현욱이는 이건 너무 쉽다고 생각했다. 그래서 가능한 한 작은 항으로 시작해 n이 등장하게 하고 싶다.

입력

첫 번째 줄에는 테스트 케이스의 개수 T가 주어진다. (T ≤ 100) 두 번째 줄부터 각 테스트 케이스에 대해 나타나게 해야 할 정수 n이 주어진다. (2 ≤ n ≤ 109)

출력

각 테스트 케이스마다 한 줄에 두 자연수 a, b를 출력한다. (0 < a ≤ b) G1 = a, G2 = b, 그리고 어떤 자연수 k에 대해 Gk = n 이다. a, b는 가능한 한 제일 작아야 하며, 이는 어떤 자연수 a', b'에 대해서 a', b'로 시작하는 Gabonacci 수열에서 n이 등장하고, b' < b 이거나 b' = b 이고 a' < a 인 a', b' 가 존재하면 안 된다는 뜻이다.

예제 입력 1

5
89
123
1000
1573655
842831057

예제 출력 1

1 1
1 3
2 10
985 1971
2 7
W3sicHJvYmxlbV9pZCI6IjEwMzI3IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YmIzOFx1YzgxY1x1ZDU3NFx1YWNiMFx1YzgwNFx1YjdiNSIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvY3JpbWVfc2NlbmUucG5nXCIgc3R5bGU9XCJmbG9hdDpyaWdodDsgaGVpZ2h0OjQyNXB4OyB3aWR0aDoyODZweFwiIFwvPjxcL3A+XHJcblxyXG48cD5cdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNWY0XHVjNzU4IFx1YjllNFx1YjgyNVx1YzVkMCBcdWJlNjBcdWM5YzQgXHVkNjA0XHVjNmIxXHVjNzc0XHViMjk0IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViMTA4XHViYjM0XHViMDk4XHViM2M0IFx1YzBhY1x1Yjc5MVx1ZDU1YyBcdWIwOThcdWJhMzhcdWM5YzAgJiMzOTtcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHViYjM4XHVjODFjXHVkNTc0XHVhY2IwXHVjODA0XHViN2I1JiMzOTsgXHVjYzQ1XHVjNzQ0IFx1YzBhY1x1YzExYyBcdWM3N2RcdWIyZTRcdWFjMDAgR2Fib25hY2NpIFx1YzIxOFx1YzVmNFx1Yzc1OCBcdWM4NzRcdWM3YWNcdWM1ZDAgXHViMzAwXHVkNTc0IFx1YzU0Y1x1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxkaXY+XHJcbjxwPlx1YjJmOVx1YzVmMFx1ZDc4OCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHVjNWY0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWM1NGNcdWFjZTAgXHVjNzg4XHVjNzQ0IFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkIFx1YmFhOFx1Yjk3OFx1YjJlNFx1YmE3NCZuYnNwOyA8YSBocmVmPVwiaHR0cHM6XC9cL3d3dy5hY21pY3BjLm5ldFwvcHJvYmxlbVwvMjc0N1wiPjI3NDdcdWJjODg8XC9hPiBcdWJiMzhcdWM4MWNcdWI5N2MgXHVkNDgwXHVjNWI0IFx1YmNmNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVhZDhjXHVjN2E1XHVkNTVjXHViMmU0LiBuXHViYzg4XHVjOWY4IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWQ1NmRcdWM3NDQgRjxzdWI+bjxcL3N1Yj5cdWM3NzRcdWI3N2MgXHVkNTYwIFx1YjU0YyBGPHN1Yj4xPFwvc3ViPiA9IDEsIEY8c3ViPjI8XC9zdWI+ID0gMlx1Yzc3NFx1YmE3MCwgXHVhZGY4IFx1Yzc3NFx1ZDZjNFx1Yzc1OCBcdWQ1NmRcdWI0ZTRcdWM3NDAgXHViYWE4XHViNDUwIFx1YmMxNFx1Yjg1YyBcdWM4MDQgMlx1YWMxYyBcdWQ1NmRcdWM3NTggXHVkNTY5XHVjNzc0XHViMmU0LiBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHVhZGMwXHViMGE5XHVjODAxIFx1YzgxNVx1Yzc1OFx1YzVkMCBcdWI1MzBcdWI3N2MgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1Yzc0MCAxLCAxLCAyLCAzLCA1LCA4LCAxMywgLiAuIC4uIFx1YzczY1x1Yjg1YyBcdWM3NzRcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzgxYyBcdWM3NzRcdWI5N2MgXHVjODgwIFx1YjM1NCBcdWM3N2NcdWJjMThcdWQ2NTRcdWQ1NzQgXHViY2Y0XHVjNzkwLiBcdWM1YjRcdWI1YTQgXHVjMjE4XHVjNWY0XHVjNzc0Jm5ic3A7XHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YzVmNFx1YWNmYyBcdWFjMTlcdWM3NDAmbmJzcDtcdWM3YWNcdWFkYzBcdWM4MDEgXHVjODE1XHVjNzU4ICZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDsmbmJzcDsmbmJzcDsmbmJzcDtHIDxzdWI+aTxcL3N1Yj4gPSBHPHN1Yj5pLTE8XC9zdWI+ICsgRzxzdWI+aS0yPFwvc3ViPiBmb3IgaSAmZ3Q7IDI8XC9wPlxyXG5cclxuPHA+XHViOTdjIFx1YjUzMFx1Yjk3NFx1YzljMFx1YjljYywgXHVjYzk4XHVjNzRjIFx1YjQ1MCBcdWQ1NmRcdWM3NDQmbmJzcDtHIDxzdWI+MTxcL3N1Yj4gJmxlOyBHPHN1Yj4yPFwvc3ViPiZuYnNwO1x1Yjk3YyBcdWI5Y2NcdWM4NzFcdWQ1NThcdWFjOGMgXHVkNTU4XHViYTc0XHVjMTFjJm5ic3A7XHVjNzg0XHVjNzU4XHViODVjIFx1YzEyNFx1YzgxNVx1ZDU2MCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1Yzc3NFx1Yjk3YyBHYWJvbmFjY2kgXHVjMjE4XHVjNWY0XHVjNzc0XHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkJm5ic3A7RzxzdWI+MTxcL3N1Yj4gPSAxLCBHPHN1Yj4yPFwvc3ViPiA9IDNcdWM3NzRcdWJhNzQsIFx1YjExMFx1YjlhYyBcdWM1NGNcdWI4MjRcdWM5YzQgXHVjMjE4XHVjNWY0XHVjNzc4IEx1Y2FzIG51bWJlcnMoMSwgMywgNCwgNywgMTEsIDE4LCAyOSwgLiAuIC4uKVx1Yjk3YyBcdWM1YmJcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjODAxXHVjODA4XHVkNTVjIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjY2FiIFx1ZDU2ZFx1Yzc0NCBcdWFjZThcdWI3N2NcdWMxMWMsIFx1YjJmOVx1YzJlMFx1Yzc3NCBcdWM2ZDBcdWQ1NThcdWIyOTQgXHVjNWI0XHViNWE0IFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yjk3YyZuYnNwO1x1YmMxOFx1YjRkY1x1YzJkYyBHYWJvbmFjY2kgXHVjMjE4XHVjNWY0XHVjNWQwXHVjMTFjIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YWM4YyBcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YmE3NCwgblx1Yzc0MCAxLCBuLTFcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IEdhYm9uYWNjaSBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgXHViNGYxXHVjN2E1XHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3ZWNcdWIwOTggXHVkNjA0XHVjNmIxXHVjNzc0XHViMjk0Jm5ic3A7XHVjNzc0XHVhYzc0IFx1YjEwOFx1YmIzNCBcdWMyN2RcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTg4XHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDU1YyBcdWM3OTFcdWM3NDAgXHVkNTZkXHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU3NCBuXHVjNzc0IFx1YjRmMVx1YzdhNVx1ZDU1OFx1YWM4YyBcdWQ1NThcdWFjZTAgXHVjMmY2XHViMmU0LjxcL3A+XHJcbjxcL2Rpdj5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKFQgJmxlOyAxMDApIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWIwOThcdWQwYzBcdWIwOThcdWFjOGMgXHVkNTc0XHVjNTdjIFx1ZDU2MCZuYnNwO1x1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4mbmJzcDsoMiAmbGU7IG4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWI0NTAgXHVjNzkwXHVjNWYwXHVjMjE4IGEsIGJcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiAoMCZuYnNwOyZsdDsmbmJzcDthICZsZTsgYikgRzxzdWI+MTxcL3N1Yj4gPSBhLCBHPHN1Yj4yPFwvc3ViPiA9IGIsIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM1YjRcdWI1YTQgXHVjNzkwXHVjNWYwXHVjMjE4IGtcdWM1ZDAgXHViMzAwXHVkNTc0IEc8c3ViPms8XC9zdWI+ID0gbiBcdWM3NzRcdWIyZTQuIGEsIGJcdWIyOTQgXHVhYzAwXHViMmE1XHVkNTVjIFx1ZDU1YyBcdWM4MWNcdWM3N2MgXHVjNzkxXHVjNTQ0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHVjNzc0XHViMjk0Jm5ic3A7XHVjNWI0XHViNWE0IFx1Yzc5MFx1YzVmMFx1YzIxOCBhJiMzOTssIGImIzM5O1x1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgYSYjMzk7LCBiJiMzOTtcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHViMjk0IEdhYm9uYWNjaSBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMgblx1Yzc3NCBcdWI0ZjFcdWM3YTVcdWQ1NThcdWFjZTAsJm5ic3A7YiYjMzk7ICZsdDsgYiBcdWM3NzRcdWFjNzBcdWIwOTggYiYjMzk7ID0gYiBcdWM3NzRcdWFjZTAgYSYjMzk7ICZsdDsgYSBcdWM3NzggYSYjMzk7LCBiJiMzOTsgXHVhYzAwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0XHViMjk0IFx1YjczYlx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDMyNyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkludGVyZXN0aW5nIEludGVnZXJzIiwiZGVzY3JpcHRpb24iOiI8cD48YSBocmVmPVwiaHR0cHM6XC9cL3hrY2QuY29tXC81ODdcL1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlczJcL2NyaW1lX3NjZW5lLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDo0MjVweDsgd2lkdGg6Mjg2cHhcIiBcLz48XC9hPlVuZG91YnRlZGx5IHlvdSBrbm93IG9mIHRoZSBGaWJvbmFjY2kgbnVtYmVycy4gU3RhcnRpbmcgd2l0aCBGPHN1Yj4xPFwvc3ViPiA9IDEgYW5kIEY8c3ViPjI8XC9zdWI+ID0gMSwgZXZlcnkgbmV4dCBudW1iZXIgaXMgdGhlIHN1bSBvZiB0aGUgdHdvIHByZXZpb3VzIG9uZXMuIFRoaXMgcmVzdWx0cyBpbiB0aGUgc2VxdWVuY2UgMSwgMSwgMiwgMywgNSwgOCwgMTMsIC4gLiAuLjxcL3A+XHJcblxyXG48cD5Ob3cgbGV0IHVzIGNvbnNpZGVyIG1vcmUgZ2VuZXJhbGx5IHNlcXVlbmNlcyB0aGF0IG9iZXkgdGhlIHNhbWUgcmVjdXJzaW9uIHJlbGF0aW9uPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjpjZW50ZXJcIj5HPHN1Yj5pPFwvc3ViPiA9IEc8c3ViPmktMTxcL3N1Yj4gKyBHPHN1Yj5pLTI8XC9zdWI+IGZvciBpICZndDsgMjxcL3A+XHJcblxyXG48cD5idXQgc3RhcnQgd2l0aCB0d28gbnVtYmVycyBHPHN1Yj4xPFwvc3ViPiAmbGU7IEc8c3ViPjI8XC9zdWI+IG9mIG91ciBvd24gY2hvaWNlLiBXZSBzaGFsbCBjYWxsIHRoZXNlIEdhYm9uYWNjaSBzZXF1ZW5jZXMuIEZvciBleGFtcGxlLCBpZiBvbmUgdXNlcyBHPHN1Yj4xPFwvc3ViPiA9IDEgYW5kIEc8c3ViPjI8XC9zdWI+ID0gMywgb25lIGdldHMgd2hhdCBhcmUga25vd24gYXMgdGhlIEx1Y2FzIG51bWJlcnM6IDEsIDMsIDQsIDcsIDExLCAxOCwgMjksIC4gLiAuLiBUaGVzZSBudW1iZXJzIGFyZSAmbmRhc2g7IGFwYXJ0IGZyb20gMSBhbmQgMyAmbmRhc2g7IGRpZmZlcmVudCBmcm9tIHRoZSBGaWJvbmFjY2kgbnVtYmVycy48XC9wPlxyXG5cclxuPHA+QnkgY2hvb3NpbmcgdGhlIGZpcnN0IHR3byBudW1iZXJzIGFwcHJvcHJpYXRlbHksIHlvdSBjYW4gZ2V0IGFueSBudW1iZXIgeW91IGxpa2UgdG8gYXBwZWFyIGluIHRoZSBHYWJvbmFjY2kgc2VxdWVuY2UuIEZvciBleGFtcGxlLCB0aGUgbnVtYmVyIG4gYXBwZWFycyBpbiB0aGUgc2VxdWVuY2UgdGhhdCBzdGFydHMgd2l0aCAxIGFuZCBuICZtaW51czsgMSwgYnV0IHRoYXQgaXMgYSBiaXQgbGFtZS4gSXQgd291bGQgYmUgbW9yZSBmdW4gdG8gc3RhcnQgd2l0aCBudW1iZXJzIHRoYXQgYXJlIGFzIHNtYWxsIGFzIHBvc3NpYmxlLCB3b3VsZCB5b3Ugbm90IGFncmVlPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIGZpcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdCBjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPm9uZSBsaW5lIHdpdGggYSBzaW5nbGUgaW50ZWdlciBuICgyICZsZTsgbiAmbGU7IDEwPHN1cD45PFwvc3VwPik6IHRoZSBudW1iZXIgdG8gYXBwZWFyIGluIHRoZSBzZXF1ZW5jZS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+b25lIGxpbmUgd2l0aCB0d28gaW50ZWdlcnMgYSBhbmQgYiAoMCAmbHQ7IGEgJmxlOyBiKSwgc3VjaCB0aGF0LCBmb3IgRzxzdWI+MTxcL3N1Yj4gPSBhIGFuZCBHPHN1Yj4yPFwvc3ViPiA9IGIsIEc8c3ViPms8XC9zdWI+ID0gbiBmb3Igc29tZSBrLiBUaGVzZSBudW1iZXJzIHNob3VsZCBiZSB0aGUgc21hbGxlc3QgcG9zc2libGUsIGkuZS4sIHRoZXJlIHNob3VsZCBiZSBubyBudW1iZXJzIGEmIzM5OyBhbmQgYiYjMzk7IHdpdGggdGhlIHNhbWUgcHJvcGVydHksIGZvciB3aGljaCBiJiMzOTsgJmx0OyBiLCBvciBmb3Igd2hpY2ggYiYjMzk7ID0gYiBhbmQgYSYjMzk7ICZsdDsgYS48XC9saT5cclxuPFwvdWw+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==