Thu Hà (nickname: Ochinchin) rất giỏi về số học nhưng lại 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 Hà đã đố cô một bài toán về dãy Fibonacci được định nghĩa như sau:

• F₁ = a, F₂ = b

• F_i = F_i−1 + F_i−2, với i > 2

Cho số nguyên dương n, cô giáo yêu cầu Hà 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 F_k = n.

Nghe tới đây, Hà đã đắ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à Hà vẫn chưa nghĩ ra lời giải cho bài toán. Cô rất căng thẳng và bắt đầu có dấu hiệu nghi ngờ về trình độ của mình. :)))) 

Để lấy lại sự tự tin, Trúc My đã quyết định nhờ các bạn thành viên đang cày môn LTNC trên UPCoder giúp đỡ. Là một cao thủ cày code, bạn sẽ giải quyết được bài toán này giúp Hà chứ?

Dữ liệu

• 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.

Ví dụ

Giới hạn

• Subtask 1 (20%): T = 500, 2 ≤ n ≤ 10⁴.

• Subtask 2 (30%): T = 500, 2 ≤ n ≤ 10⁶.

• Subtask 3 (50%): T = 2000, 2 ≤ n ≤ 10⁹.