Mô tả

Cho một dãy số A_n được xác định bởi công thức truy hồi: A₁ = 1; A₂ = 3; A_n = 2 × A_n-1 - A_n-2 + 2 với mọi n ≥ 3.

Theo công thức trên, ta có dãy: 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.

Input

Một dòng duy nhất chứa số nguyên dương n (1 < n < 109).

Output

Ghi ra số k theo yêu cầu.

Ví dụ

input
3

output
10

Ghi chú

Với n = 3 ta có A₃ × A₄ = 7 × 13 = 91 = A₁₀ nên k = 10.