在 Byteland 有 $n$ 个海盗宝箱，编号为 $1, 2, \dots, n$。第 $i$ 个宝箱位于平面上的点 $(x_i, y_i)$，其价值为 $w_i$。注意 $w_i$ 可能是负数，因为海盗可能在宝箱里放入了毒气。当你打开第 $i$ 个海盗宝箱时，你将获得 $w_i$ 的价值。

你想要从这些海盗宝箱中获利。你可以选择一个边与坐标轴平行的矩形，然后打开该矩形内部或边界上的所有宝箱。注意，你必须打开该范围内的所有宝箱，无论其价值是正还是负。但你可以选择一个内部没有任何宝箱的矩形，从而获得零价值。

请编写一个程序，求出矩形所能获得的最大总价值。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 2000$)，表示海盗宝箱的数量。

接下来的 $n$ 行，每行包含三个整数 $x_i, y_i$ 和 $w_i$ ($-10^9 \le x_i, y_i, w_i \le 10^9$)，描述第 $i$ 个海盗宝箱。

保证所有测试用例中 $n$ 的总和不超过 $10\,000$。

输出格式

对于每个测试用例，输出一行，包含一个整数：最大总价值。

样例

样例输入 1

2
4
1 1 50
2 1 50
1 2 50
2 2 -500
2
-1 1 5
-1 1 1

样例输出 1

100
6