Cho một dãy số {A_n} được xác định bởi công thức truy hồi sau:

A₁ = 1; A₂ = 3;  A_n = 2A_n-1 – A_n-2 + 2 với mọi nÎN, n ≥ 3.

Theo công thức trên, ta có dãy số:

A₁ = 1; A₂ = 3; A₃ = 7; A₄ = 13; A₅ = 21; ...

Yêu cầu: Cho trước số nguyên dương n. Hãy tìm số nguyên dương k sao cho A_k = A_n.A_n+1.

Dữ liệu vào: Đọc từ file văn bản DAYSO.INP một số nguyên dương n            (1 < n < 10⁹).

Dữ liệu ra: Ghi ra file văn bản DAYSO.OUT số k theo yêu cầu trên.

Ví dụ: