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.
Professor 想要在黑板上从 1 开始依次写下每一个正整数。每写下一个正整数 a ，他将判断在之前写下的数字中是否存在 b ，使得满足下列任意一个条件：
a+b×b≡0(mod k) b+a×a≡0(mod k)找到所有 b ，并连接一条有向边 (a,b) 。当所连接的某些边形成环路时，停止。
给定模数 k ，问对于每个询问 k 的停止时写下的正整数 a 。若永远不会停止，则输出 -1 。
在无从下手的时候，考虑先找到某些特殊点。通过二式 b+a×a≡0(mod k) 。可以判断出存在有向边 (k−1,1) , (2⋅k−1,1) , (3⋅k−1,1) … 通过一式可以看到
a=k−1b=2⋅k−1a+b×b≡?(mod k)⎫⎭⎬⎪⎪⟹(k−1)+(2⋅k−1)2≡0(mod k) 故又存在有向边 (2⋅k−1,k−1) 。此时必然存在环路。此题对于任意的 k 都必然存在解，且最大为 2⋅k−1 。在明确上述问题后，暴力扫描 [1, 2k-1] 即可。对于判断环路，可通过并查集解决，当准备直接相连的两边已经在同一个集合内时，说明出现环路。
