Dãy Fibonacci là một dãy số nguyên không âm, trong đó mỗi số (kể từ số thứ ba) bằng tổng của hai số đứng ngay trước nó.

Dãy Fibonacci được định nghĩa như sau:

• F₀ = 0
• F₁ = 1
• Fₙ = Fₙ₋₁ + Fₙ₋₂, với n ≥ 2.

Các phần tử đầu tiên của dãy Fibonacci là:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Ví dụ, số Fibonacci có giá trị 8 nằm ở vị trí 6 (F₆ = 8), số Fibonacci có giá trị 13 nằm ở vị trí 7 (F₇ = 13).

Cho một số nguyên dương N.

Yêu cầu: Hãy tìm số Fibonacci lớn nhất có giá trị nhỏ hơn N, đồng thời xác định vị trí của số đó trong dãy Fibonacci.

Lưu ý:

• Chỉ xét các số Fibonacci nhỏ hơn N (không bao gồm N).
• Nếu một giá trị xuất hiện ở nhiều vị trí, chọn vị trí có chỉ số lớn nhất.
• Vị trí của phần tử đầu tiên được đánh số từ 0.

Input

Một dòng duy nhất chứa số nguyên dương N.

Output

In ra hai số nguyên i và Fᵢ, cách nhau một dấu cách, trong đó:

• i là vị trí của số Fibonacci tìm được.
• Fᵢ là giá trị số Fibonacci lớn nhất nhỏ hơn N.

Constraints

• 1 ≤ N ≤ 10¹⁸.
• Thời gian thực thi: 1 giây.
• Bộ nhớ: 256 MB.

Example 1

Input

10

Output

6 8

Explanation

Dãy Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, ...

Số Fibonacci lớn nhất nhỏ hơn 10 là 8, nằm ở vị trí 6.

Example 2

Input

13

Output

6 8

Explanation

13 là một số Fibonacci nhưng yêu cầu bài toán là tìm số nhỏ hơn N. Vì vậy, kết quả là 8 tại vị trí 6.

Example 3

Input

1

Output

0 0

Explanation

Số Fibonacci lớn nhất nhỏ hơn 1 là 0 tại vị trí 0.

Example 4

Input

2

Output

2 1

Explanation

Giá trị 1 xuất hiện ở vị trí 1 và 2. Theo yêu cầu, chọn vị trí lớn nhất là 2.