Bờm rất giỏi về số học. Cậu ta rất hay chán nản vì những bài tập ở trên lớp. Nhận thấy điều này, cô giáo của Bờm đã đố cậu một bài toán về dãy Fibonacci được định nghĩa như sau:
F1 = a, F2 = b
Fi = Fi-1 + Fi-2 , với i > 2
Cho số nguyên dương n, cô giáo yêu cầu Bờm tìm ra hai số nguyên dương a và b (a < b) sau cho tồn tại một số nguyên dương k thỏa mãn Fk = n.
Nghe tới đây, Bờm đã đắc chí đưa ra câu trả lời vội vàng: “Thế thì a = n là được chứ gì”. Tuy nhiên, cô giáo đã cho thêm điều kiện sau: “Tìm ra a và b sao cho b đạt giá trị nhỏ nhất, nếu có nhiều đáp án có giá trị b bằng nhau, đưa ra đáp án có giá trị a nhỏ nhất”.
Một tuần trôi qua mà Bờm vẫn chưa nghĩ ra lời giải cho bài toán. Cậu rất căng thẳng và bắt đầu có dấu hiệu nghi ngờ về trình độ của mình. Bạn hãy giải quyết được bài toán này giúp Bờm?
Dữ liệu: có cấu trúc như sau:
- Dòng đầu tiên chứa số nguyên dương T tương ứng với số lượng bộ dữ liệu.
- T dòng tiếp theo, mỗi dòng chứa một số nguyên dương n duy nhất.
Kết quả: Gồm T dòng, mỗi dòng gồm hai số nguyên dương a và b tương ứng với kết quả bài toán.
|
INPUT |
OUTPUT |
|
5 |
1 1 |
|
2 |
2 2 |
|
4 |
1 1 |
|
89 |
1 3 |
|
123 |
2 10 |
|
1000 |
|
Giới hạn:
- Subtask 1 (20%): T = 500, 2 ≤ n ≤ 104.
- Subtask 2 (30%): T = 500, 2 ≤ n ≤ 106.
- Subtask 3 (50%): T = 2000, 2 ≤ n ≤ 109.