404689: GYM101608 M Winning Cells

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 × 10⁴), 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 ≤ 10⁹), 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.

3
2 1
3 1
9 4

2
4
64