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.
The 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.
You 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.
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.
For each test case, print a single line that contains the number cells you can choose as a starting position to win the game.
## Input
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.
## Output
For each test case, print a single line that contains the number cells you can choose as a starting position to win the game.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case, let $ n, k \in \mathbb{Z} $ with $ 1 \leq k < n \leq 10^9 $.
The 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.
**Constraints**
1. $ 1 \leq T \leq 2 \times 10^4 $
2. For each test case: $ 1 \leq k < n \leq 10^9 $
**Objective**
Count 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.
**Key Insight**
This 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 $.
Each move reduces either $ d_r $ or $ d_c $ by $ 1 $ to $ k $.
This is equivalent to a variant of **Kayles** or **subtraction game** on two independent piles, with move limit $ k $.
The losing positions (P-positions) are those where $ d_r \equiv d_c \pmod{k+1} $.
Thus, winning positions for the first player are those where $ d_r \not\equiv d_c \pmod{k+1} $.
Total positions: $ n^2 - 1 $ (excluding $ (1,1) $).
Number of losing positions (where $ d_r \equiv d_c \pmod{k+1} $, $ (d_r, d_c) \neq (0,0) $):
Let $ m = k+1 $.
For each residue $ r \in \{0, 1, \dots, m-1\} $, count number of $ d \in [0, n-1] $ with $ d \equiv r \pmod{m} $:
Let $ q = \left\lfloor \frac{n-1}{m} \right\rfloor $, $ r_{\max} = (n-1) \bmod m $.
Then for each residue $ r $, count is $ q + 1 $ if $ r \leq r_{\max} $, else $ q $.
Number of pairs $ (d_r, d_c) $ with $ d_r \equiv d_c \pmod{m} $:
$ \sum_{r=0}^{m-1} c_r^2 $, where $ c_r $ is count of $ d \equiv r \pmod{m} $.
Subtract 1 for $ (0,0) $: total losing positions = $ \sum_{r=0}^{m-1} c_r^2 - 1 $.
Then 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 $
**Final Objective**
For each test case, compute:
$$
\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}
$$