問題 G1 とは制約のみが異なります

問題文

G1 - Genuine Multiple Dependencies [Easy] と同じ状況を考えます

下記の制約下で問題を解いてください．

• $1 \leq T \leq \bold{10^4}$
• $0 \leq N \leq \bold{3000}$
• $1 \leq X \leq \bold{3000}$
• 入力はすべて整数である

サンプル

G1 と同一のものです．

11
0 1
1 1
1 3
2 6
2 10
6 8
5 14
12 7
14 21
0 300
300 1

1
1
3
21
55
1716
8568
18564
393731287
1
1