{"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] 必须不少于两个。\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 \\in \\mathbb{N} $, $ 1 \\leq n \\leq 10^5 $.\n\nA move consists of replacing a 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: $ a_i = a_1 - (i-1) $, and the total sum is:\n$$\n\\sum_{i=1}^k a_i = \\sum_{j=0}^{k-1} (a_1 - j) = k a_1 - \\frac{k(k-1)}{2} = n.\n$$\nThus, for a valid move, there must exist integers $ k \\geq 2 $ and $ a_1 \\geq k $ such that:\n$$\nk a_1 - \\frac{k(k-1)}{2} = n.\n$$\nRearranged:\n$$\na_1 = \\frac{n + \\frac{k(k-1)}{2}}{k} = \\frac{2n + k(k-1)}{2k}.\n$$\nThis must be an integer, so $ 2n + k(k-1) \\equiv 0 \\pmod{2k} $.\n\nDefine the game as an impartial combinatorial game under normal play: positions are pile sizes, moves are as above, and a player unable to move loses.\n\nLet $ G(n) $ denote the Grundy number of a pile of size $ n $. The base case: $ G(1) = 0 $ (no valid move).\n\nFor $ n \\geq 2 $, define:\n$$\nG(n) = \\mathrm{mex} \\left\\{ \\bigoplus_{i=1}^k G(a_i) \\mid \\text{valid partition of } n \\text{ into } k \\geq 2 \\text{ consecutive decreasing piles} \\right\\}.\n$$\nBut since the piles in a move are **consecutive integers**, and the game is played on a single pile (no multiple independent piles initially), and each move replaces one pile with multiple piles, the resulting position is a **disjunctive sum** of the new piles.\n\nSo from $ n $, moving to piles $ a_1, a_2, \\dots, a_k $ leads to position with Grundy number:\n$$\nG(a_1) \\oplus G(a_2) \\oplus \\dots \\oplus G(a_k).\n$$\n\nThus:\n$$\nG(n) = \\mathrm{mex} \\left\\{ \\bigoplus_{i=1}^k G(a_i) \\ \\middle|\\  \\exists k \\geq 2, \\ a_i = a_1 - (i-1), \\ \\sum_{i=1}^k a_i = n \\right\\}.\n$$\n\nThe first player (Serozha) wins if $ G(n) \\ne 0 $; loses if $ G(n) = 0 $.\n\nIf Serozha wins, output the **minimal** $ k \\geq 2 $ such that:\n1. The sequence $ a_1 > a_2 > \\dots > a_k > 0 $ with $ a_i - a_{i+1} = 1 $ sums to $ n $,\n2. The resulting position $ \\bigoplus_{i=1}^k G(a_i) = 0 $ (i.e., leaves Gena in a losing position).\n\nIf no such $ k $ exists (i.e., Gena wins), output $-1$.\n\n---\n\n**Formal Output Specification:**\n\nLet $ S(n) $ be the set of all $ k \\geq 2 $ such that there exists integer $ a_1 \\geq k $ satisfying:\n$$\nn = \\sum_{i=0}^{k-1} (a_1 - i) = k a_1 - \\frac{k(k-1)}{2}.\n$$\nFor each $ k \\in S(n) $, define the pile sizes $ a_i = a_1 - (i-1) $, $ i = 1, \\dots, k $, and compute:\n$$\ng_k = \\bigoplus_{i=1}^k G(a_i).\n$$\n\nThen:\n\n- If $ G(n) = 0 $, output $-1$.\n- Else, output $ \\min \\{ k \\in S(n) \\mid g_k = 0 \\} $.\n\nWhere $ G(m) $ is recursively defined for $ m = 1 $ to $ n $ as:\n$$\nG(1) = 0,\n$$\n$$\nG(m) = \\mathrm{mex} \\left\\{ \\bigoplus_{i=1}^k G(a_i) \\ \\middle|\\  k \\geq 2,\\ \\sum_{i=1}^k a_i = m,\\ a_i = a_1 - (i-1),\\ a_1 \\in \\mathbb{Z}^+ \\right\\}.\n$$","simple_statement":null,"has_page_source":false}