ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Open Personal Contest 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Crazy Professor

Time limit: 1.0 second
Memory limit: 64 MB
Professor Nathan Mathan is crazy about mathematics. For an unknown reason, he started to write on the blackboard all positive integers starting from 1. After writing a new number a, Professor draws lines connecting it with all the numbers b that are already on the blackboard and satisfy at least one of the conditions:
  • b + a · a ≡ 0 (mod k),
  • a + b · b ≡ 0 (mod k),
where k is some parameter.
Nobody can persuade him to stop this meaningless procedure. Professor says that he will stop as soon as there appears a cycle in the graph of the numbers on the blackboard. But only Professor knows when that will happen and whether it will happen at all. Help his colleagues determine after which number he will stop.


You are given the integer k (1 ≤ k ≤ 100000).


Output the number after which the first cycle will appear in the graph. If it never happens, output −1.




In example after Professor had written all integers from 1 to 4 the graph contained edges (1, 3) and (2, 4). After writing number 5, Professor connects it with numbers 1 and 3, so the cycle 1-5-3-1 appears in the graph.
Problem Author: Pavel Egorov
Problem Source: USU Open Personal Contest 2009 (February 28, 2009)
To submit the solution for this problem go to the Problem set: 1682. Crazy Professor