题目描述

$CRY$ 正在忙着给国庆新生赛出题，他想出了 $n$ 道题目，每道题目需要花费 $a_i$ 的精力出题。因为去年新生赛给 $CRY$ 留下不小的心理阴影，于是他变得心狠手辣，他今年出的每道题都会对选手造成一定的心理阴影，具体表现为一个以 $(0,0)$ 和 $(x_i,y_i)$ 为顶点的矩形,其中 $x_i$ 和 $y_i$ 都是正整数。$CRY$ 的愉悦值为所有矩形的面积并的值减去出题所耗费的精力，请你帮助残忍的 $CRY$ 选择适当的题目最大化他的愉悦值。

当然，由于 $CRY$ 出题水平很高，保证不存在两个矩形使得其中一个被另外一个完全包含!

输入格式

第一行一个整数 $T(1\leq T\leq 10)$ 代表数据组数

每组数据第一行数字 $n(1\leq n \leq 5*10^3)$。

下面 $n$ 行，每行三个数 $x_i,\ y_i,\ a_i(1\leq x_i,y_i \leq 10^9,0\leq a_i \leq x_i \times y_i)$。

输出格式

$T$ 行每行一个整数表示最大愉悦值。

样例

输入样例

1
3
1 5 0
3 4 2
5 1 3

输出样例

11

样例解释

选取第一个和第二个矩形，总面积为 $13$，消耗精力为 $2$。

数据范围与提示

注意，是矩形的面积并。