Профессор Натан Матанович просто одержим математикой. Он зачем-то стал выписывать на доске по порядку все целые положительные числа, начиная с единицы. После того, как на доске появляется очередное число a, профессор соединяет его отрезками со всеми написанными ранее числами b такими, что выполняется хотя бы одно из двух условий:

• b + a · a ≡ 0 (mod k),
• a + b · b ≡ 0 (mod k),

где k — некоторый заданный параметр.

И никто не смог уговорить его прекратить это бессмысленное занятие. Он сказал, что остановится лишь тогда, когда в графе чисел на доске появится цикл. Но когда это произойдёт и произойдёт ли вообще, известно только ему одному. Помогите его коллегам определить, после какого числа профессор остановится.

В единственной строке дано целое число k (1 ≤ k ≤ 100000).

Если в графе на доске рано или поздно появится цикл, выведите число, после выписывания которого это произойдёт. Если же цикл в таком графе не появится никогда, выведите −1.

В примере после того, как профессор выписал все числа от 1 до 4, граф содержит рёбра (1, 3) и (2, 4). Написав число 5, профессор соединяет его отрезками с числами 1 и 3, таким образом, в графе появляется цикл 1-5-3-1.