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

~A_1 = 1, A_2 = 3, A_n = 2A_{n - 1} – A_{n - 2} + 2~ với mọi ~n~ thuộc N, ~(n ≥ 3)~.

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

~A_1 = 1; A_2 = 3; A_3 = 7; A_4 = 13; A_5 = 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

• Là một số nguyên dương ~n~ được nhập từ bàn phím ~(1 < n < 10^9)~

Output

• Là một số nguyên ~k~ thỏa mãn điều kiện trên

Scoring

• Không có giới hạn gì thêm

Ví dụ

Sample Input

3

Sample Output

10

Giải thích ví dụ: Với ~n~ = 3 ta có ~A_3.A_4~ = 7.13 = 91 = ~A_{10}~ nên ~k~ = 10.