{"raw_statement":[{"iden":"statement","content":"Two best friends Serozha and Gena play a game.\n\nInitially there is one pile consisting of _n_ stones on the table. During one move one pile should be taken and divided into an arbitrary number of piles consisting of _a_1 > _a_2 > ... > _a__k_ > 0 stones. The piles should meet the condition _a_1 - _a_2 = _a_2 - _a_3 = ... = _a__k_ - 1 - _a__k_ = 1. Naturally, the number of piles _k_ should be no less than two.\n\nThe friends play in turns. The player who cannot make a move loses. Serozha makes the first move. Who will win if both players play in the optimal way?"},{"iden":"input","content":"The single line contains a single integer _n_ (1 ≤ _n_ ≤ 105)."},{"iden":"output","content":"If Serozha wins, print _k_, which represents the minimal number of piles into which he can split the initial one during the first move in order to win the game.\n\nIf Gena wins, print \"-1\" (without the quotes)."},{"iden":"examples","content":"Input\n\n3\n\nOutput\n\n2\n\nInput\n\n6\n\nOutput\n\n\\-1\n\nInput\n\n100\n\nOutput\n\n8"}],"translated_statement":[{"iden":"statement","content":"两个最好的朋友 Serozha 和 Gena 玩一个游戏。\n\n最初桌上有且仅有一堆包含 #cf_span[n] 个石子的石堆。每一步，玩家必须选择一堆石子，并将其拆分为任意数量的石堆，这些石堆的石子数满足 #cf_span[a1 > a2 > ... > ak > 0]，且必须满足条件 #cf_span[a1 - a2 = a2 - a3 = ... = ak - 1 - ak = 1]。显然，石堆的数量 #cf_span[k] 至少为 2。\n\n两位玩家轮流进行操作，无法进行操作的玩家输掉游戏。Serozha 先手。如果双方都采取最优策略，谁会获胜？\n\n输入仅一行，包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])。\n\n如果 Serozha 获胜，请输出 #cf_span[k]，表示他在第一步中将初始石堆拆分成的最少石堆数量以确保获胜。\n\n如果 Gena 获胜，请输出 \"-1\"（不含引号）。"},{"iden":"input","content":"输入仅一行，包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 105])。"},{"iden":"output","content":"如果 Serozha 获胜，请输出 #cf_span[k]，表示他在第一步中将初始石堆拆分成的最少石堆数量以确保获胜。如果 Gena 获胜，请输出 \"-1\"（不含引号）。"},{"iden":"examples","content":"输入\n3\n输出\n2\n\n输入\n6\n输出\n-1\n\n输入\n100\n输出\n8"}],"sample_group":[],"show_order":[],"formal_statement":"Let $ n $ be the initial number of stones.\n\nA move consists of replacing one pile of size $ n $ with $ k \\geq 2 $ piles of sizes $ a_1 > a_2 > \\dots > a_k > 0 $ such that:\n$$\na_i - a_{i+1} = 1 \\quad \\text{for all } 1 \\leq i < k.\n$$\nThis implies the pile sizes form a consecutive decreasing sequence:  \n$$\na_i = a_1 - (i - 1), \\quad \\text{so} \\quad a_k = a_1 - (k - 1).\n$$\nThe total number of stones is:\n$$\n\\sum_{i=1}^k a_i = \\sum_{j=0}^{k-1} (a_1 - j) = k a_1 - \\frac{(k-1)k}{2}.\n$$\nSet equal to $ n $:\n$$\nk a_1 - \\frac{k(k-1)}{2} = n \\quad \\Rightarrow \\quad a_1 = \\frac{n + \\frac{k(k-1)}{2}}{k} = \\frac{2n + k(k-1)}{2k}.\n$$\nFor $ a_1 $ to be a positive integer, $ \\frac{2n + k(k-1)}{2k} \\in \\mathbb{Z}^+ $, and since $ a_k = a_1 - (k - 1) > 0 $, we require:\n$$\na_1 \\geq k \\quad \\Rightarrow \\quad \\frac{2n + k(k-1)}{2k} \\geq k \\quad \\Rightarrow \\quad 2n + k(k-1) \\geq 2k^2 \\quad \\Rightarrow \\quad 2n \\geq k^2 + k.\n$$\nThus, a valid move exists for $ k \\geq 2 $ if and only if:\n$$\nk(k+1) \\leq 2n \\quad \\text{and} \\quad \\frac{2n + k(k-1)}{2k} \\in \\mathbb{Z}.\n$$\n\nLet $ G(n) $ denote the Grundy number (nimber) of a pile of size $ n $.\n\nBase case: $ G(1) = 0 $ (no move possible).\n\nFor $ n \\geq 2 $:\n$$\nG(n) = \\mathrm{mex} \\left\\{ \\bigoplus_{i=1}^k G(a_i) \\,\\middle|\\, \\text{valid split into } k \\geq 2 \\text{ piles with consecutive decreasing sizes summing to } n \\right\\}.\n$$\nBut since the split produces piles of sizes $ a_1, a_1 - 1, \\dots, a_1 - k + 1 $, and the game is impartial with independent piles, the Grundy value of the resulting position is:\n$$\n\\bigoplus_{j=0}^{k-1} G(a_1 - j).\n$$\n\nWe are to compute $ G(n) $ for $ 1 \\leq n \\leq 10^5 $.\n\nIf $ G(n) = 0 $, then the first player (Serozha) loses → output \"-1\".\n\nIf $ G(n) \\ne 0 $, then Serozha wins. We must find the **minimal** $ k \\geq 2 $ such that:\n1. $ k(k+1) \\leq 2n $,\n2. $ \\frac{2n + k(k-1)}{2k} \\in \\mathbb{Z} $,\n3. The resulting position has Grundy number 0 (i.e., the move leads to a losing position for Gena).\n\nThat is, find minimal $ k \\geq 2 $ satisfying (1), (2), and:\n$$\n\\bigoplus_{j=0}^{k-1} G\\left( \\frac{2n + k(k-1)}{2k} - j \\right) = 0.\n$$\n\n---\n\n**Formal Output Requirement:**\n\nGiven $ n \\in [1, 10^5] $:\n\n- If $ G(n) = 0 $, output $-1$.\n- Else, output the minimal $ k \\geq 2 $ such that:\n  $$\n  \\begin{cases}\n  k(k+1) \\leq 2n, \\\\\n  \\dfrac{2n + k(k-1)}{2k} \\in \\mathbb{Z}^+, \\\\\n  \\displaystyle \\bigoplus_{j=0}^{k-1} G\\left( \\left\\lfloor \\frac{2n + k(k-1)}{2k} \\right\\rfloor - j \\right) = 0.\n  \\end{cases}\n  $$\n\n(Note: The floor is redundant since condition 2 ensures integrality.)","simple_statement":null,"has_page_source":false}