Loli mới được học về phép tính lũy thừa. Trong buổi học đó, thầy giáo giao cho Loli một bài khá khoai:

Cho một số nguyên dương ~k~, hãy tìm số nguyên dương ~x~ lớn nhất sao cho ~x~ thỏa mãn hai điều kiện:

• ~1\le x < k~;
• ~x! + (x-1)!~ là bội của ~k~, nói cách khác ~x! + (x-1)!~ chia hết cho ~k~.

Input:

Lấy từ tệp WTFACT.INP gồm:

• Một dòng duy nhất ghi số nguyên dương ~k~ ~(2\le k \le 10^9)~.

Output:

Ghi ra tệp WTFACT.OUT gồm:

• Một số nguyên dương là số ~x~ cần tìm. Nếu không có ~x~ thỏa mãn, in ra ~-1~.

Sample Input 1

8

Sample Output 1

7

Giải thích

• Ở test đầu, ~7! + 6! = 5040 + 720 = 5760~, và ~5760~ chia hết cho ~8~.

Ràng buộc

• Có ~20\%~ test có ~k\le 10~;
• Có ~20\%~ test có ~k\le 10^3~;
• Có ~20\%~ test có ~k\le 10^4~;
• Các test còn lại không có ràng buộc gì thêm.