{"problem":{"name":"M. Winning Cells","description":{"content":"You and your friend decided to play a new game using a squared chessboard of size n × n and one rook. Rows are numbered from 1 to n from top to bottom, and columns are numbered from 1 to n from left t","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10160M"},"statements":[{"statement_type":"Markdown","content":"You and your friend decided to play a new game using a squared chessboard of size n × n and one rook. Rows are numbered from 1 to n from top to bottom, and columns are numbered from 1 to n from left to right. Each cell is identified by a pair (r, c) which means that the cell is located at row r and column c.\n\nThe rules are simple, you and your friend will take turns, and you will start first. In each turn a player can move the rook at least 1 cell, and at most k cells in only one direction, either up or left, without going outside the chessboard. The player who moves the rook to the top-left cell (1, 1) wins.\n\nYou will choose the starting position for the rook. You are not allowed to choose the top-left cell. If you both will play optimally, how many cells can you choose as a starting position to win the game.\n\nThe first line of input contains an single integer T (1 ≤ T ≤ 2 × 104), the number of test cases.\n\nEach test case consists of a single line that contains two space-separated integers n and k (1 ≤ k < n ≤ 109), where n is the size of the chessboard, and k is the maximum allowed move.\n\nFor each test case, print a single line that contains the number cells you can choose as a starting position to win the game.\n\n## Input\n\nThe first line of input contains an single integer T (1 ≤ T ≤ 2 × 104), the number of test cases.Each test case consists of a single line that contains two space-separated integers n and k (1 ≤ k < n ≤ 109), where n is the size of the chessboard, and k is the maximum allowed move.\n\n## Output\n\nFor each test case, print a single line that contains the number cells you can choose as a starting position to win the game.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ n, k \\in \\mathbb{Z} $ with $ 1 \\leq k < n \\leq 10^9 $.  \nThe game is played on an $ n \\times n $ grid; the rook starts at some cell $ (r, c) \\neq (1,1) $, and players alternately move it **only up or left** by $ 1 $ to $ k $ cells. The player who moves the rook to $ (1,1) $ wins.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 2 \\times 10^4 $  \n2. For each test case: $ 1 \\leq k < n \\leq 10^9 $\n\n**Objective**  \nCount the number of starting positions $ (r, c) \\in \\{1, \\dots, n\\}^2 \\setminus \\{(1,1)\\} $ such that the first player has a winning strategy under optimal play.\n\n**Key Insight**  \nThis is an impartial game equivalent to a two-pile Nim variant with move limits. Define the state by distances: $ d_r = r - 1 $, $ d_c = c - 1 $. The game ends when $ d_r = d_c = 0 $.  \nEach move reduces either $ d_r $ or $ d_c $ by $ 1 $ to $ k $.  \nThis is equivalent to a variant of **Kayles** or **subtraction game** on two independent piles, with move limit $ k $.\n\nThe losing positions (P-positions) are those where $ d_r \\equiv d_c \\pmod{k+1} $.  \nThus, winning positions for the first player are those where $ d_r \\not\\equiv d_c \\pmod{k+1} $.\n\nTotal positions: $ n^2 - 1 $ (excluding $ (1,1) $).  \nNumber of losing positions (where $ d_r \\equiv d_c \\pmod{k+1} $, $ (d_r, d_c) \\neq (0,0) $):  \nLet $ m = k+1 $.  \nFor each residue $ r \\in \\{0, 1, \\dots, m-1\\} $, count number of $ d \\in [0, n-1] $ with $ d \\equiv r \\pmod{m} $:  \nLet $ q = \\left\\lfloor \\frac{n-1}{m} \\right\\rfloor $, $ r_{\\max} = (n-1) \\bmod m $.  \nThen for each residue $ r $, count is $ q + 1 $ if $ r \\leq r_{\\max} $, else $ q $.  \nNumber of pairs $ (d_r, d_c) $ with $ d_r \\equiv d_c \\pmod{m} $:  \n$ \\sum_{r=0}^{m-1} c_r^2 $, where $ c_r $ is count of $ d \\equiv r \\pmod{m} $.  \nSubtract 1 for $ (0,0) $: total losing positions = $ \\sum_{r=0}^{m-1} c_r^2 - 1 $.\n\nThen winning positions = $ (n^2 - 1) - \\left( \\sum_{r=0}^{m-1} c_r^2 - 1 \\right) = n^2 - \\sum_{r=0}^{m-1} c_r^2 $\n\n**Final Objective**  \nFor each test case, compute:\n$$\n\\boxed{n^2 - \\sum_{r=0}^{k} \\left( \\left\\lfloor \\frac{n-1}{k+1} \\right\\rfloor + \\mathbf{1}_{r \\leq (n-1) \\bmod (k+1)} \\right)^2}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10160M","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}