#P17840. [ONTAK 2021]MEX

[ONTAK 2021]MEX

Mex 棋盘

在 N×NN\times N 的棋盘上填入非负整数,左下角坐标是 (1,1)(1,1)。格子 (x,y)(x,y) 的数值等于以下格子的数值集合的 mex:

  • 同一行中横坐标小于 xx 的格子;
  • 同一列中纵坐标小于 yy 的格子;
  • 所有 (x−t,y−t)(x-t,y-t),其中 t≥1t\ge1 且该格子在棋盘内。

mex 是集合中没有出现的最小非负整数,空集的 mex 为 00。

有 QQ 个询问。每个询问给出 N,kN,k,求 N×NN\times N 棋盘中数值等于 kk 的格子数。

输入格式

第一行 QQ,接下来 QQ 行各包含 N,kN,k。

输出格式

每个询问输出一行答案。

数据范围

1≤Q,N≤5000001\le Q,N\le500000,0≤k≤100\le k\le10。

样例

4
3 0
2 1
4 6
4 2
3
2
1
3