{"raw_statement":[{"iden":"statement","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"},{"iden":"input","content":"The 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."},{"iden":"output","content":"For each test case, print a single line that contains the number cells you can choose as a starting position to win the game."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**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$$","simple_statement":"You and your friend play a game on an n×n chessboard with a rook. You start first. Each turn, a player can move the rook 1 to k cells either left or up. The player who moves the rook to (1,1) wins. You choose the starting position (not (1,1)). How many starting positions let you win if both play optimally?","has_page_source":false}