問題文

高橋君は世界征服のために Q 個のウイルスを作ることにしました。そのためには塩基列を考えることが重要ですが、あまりに候補が多すぎるのであなたに助けを求めてきました。

x 番目に作りたいウイルスの塩基列は、長さ N_x の数列 A_1, A_2, \cdots, A_{N_x} であって、以下の条件を満たすものとして表せます。

• 各要素は 0, 1 のどちらか。
• 回文である。つまり、 1 \leq i \leq N_x について、 A_i = A_{N_x+1-i} が満たされる。
• 転倒数は K_x である。ただし、転倒数とは、整数組 (i, j) であって、i < j かつ A_i > A_j となるものの個数を表す。

制約

• 1 \leq Q \leq 10^5
• 1 \leq N_i \leq 10^5
• 0 \leq K_i \leq N_i(N_i - 1) / 2
• 入力はすべて整数

入力例 1

4
3 0
3 1
3 2
3 3

出力例 1

2
2
0
0

入力例 2

5
4 2
5 3
6 4
16 8
869 120

出力例 2

2
4
6
0
0