Trò chơi thú vị

Có một đống gồm $n$ viên sỏi trên bàn. Hai người chơi luân phiên thực hiện nước đi.

Trong một nước đi, người chơi chọn một đống bất kỳ và chia nó thành nhiều đống mới có số sỏi lần lượt là $a_1>a_2>\dots >a_k>0$, sao cho $a_1-a_2=a_2-a_3=\dots =a_{k-1}-a_k=1$. Nói cách khác, đống được chia thành $k$ đống mà số sỏi là các số nguyên liên tiếp. Số đống $k$ phải không nhỏ hơn $2$.

Hai người chơi lần lượt đi, người đi trước là người thứ nhất. Người nào đến lượt mà không thể thực hiện được nước đi nào thì thua. Cả hai đều chơi tối ưu.

Hãy xác định ai thắng. Nếu người thứ nhất thắng, in ra $k$ nhỏ nhất, tức số đống nhỏ nhất mà người thứ nhất có thể chia đống ban đầu ở nước đi đầu tiên để giành chiến thắng.

Dữ liệu vào

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

Dữ liệu ra

Nếu người thứ nhất thắng, in ra số nguyên $k$ nhỏ nhất là số đống mà người thứ nhất chia đống ban đầu ở nước đi đầu tiên để thắng.

Nếu người thứ hai thắng, in ra $-1$.

Ràng buộc

• $1\le n\le {10}^5$

Ví dụ