GYM-101608-M

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.

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.

Example

Input

3
2 1
3 1
9 4

Output

2
4
64

题意：

有一个n×nn\times n的棋盘，有个棋子，A和B依次移动这个棋子。
每次移动[1,k][1,k]步。
只能沿一个方向走。
只能向左或上走。
A先走。
把棋子移到左上角的赢。
both will play optimally。
现在由A选择一个起点并开始移动，有多少点是可以让A赢的。
把能赢得位置画出来找规律。
以k=3k=3为例
k==3
为了计算方便，将其分块

分成边长k+1k+1的正方形，由三部分：
1.完整的正方形里面有k2+kk^2+k个格子为必胜的。
2.四周的不完整的矩形。
3.右下角小正方形。
计算即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<stdio.h>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<queue>
#include<string>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long ll;
int main()
{
	freopen("chess.in", "r", stdin);
	int T;
	scanf("%d", &T);
	while (T--)
	{
		ll n, k;
		scanf("%lld%lld", &n, &k);
		ll ans = 0;
		ll nei = (n / (k + 1));
		ans += nei * nei* (k*k + k);
		ll wai = n % (k + 1);
		if (wai == 0)
		{
			printf("%lld\n", ans);
			continue;
		}
		ans += wai*k * nei * 2;
		ans += (wai - 1) *(wai-1)+(wai-1);
		printf("%lld\n", ans);
	}
}