温暖的阳光，凉爽的微风，美好的一天，而那个女孩在混乱中追寻。六花伸出手，头顶戴上了花环，看到了 LCR 那永恒的微笑。梦境最终醒来，但疑虑永远不会消失。最终，在对 LCR 一无所知的情况下，六花被邀请到了西安的传统艺术街区——书院门。

“用现有的电线够吗？”

“没问题……那些领导只关心为了学校和他们自己的‘成就’去扩大 EC Final。所有的杂活都是我们的。把那些接线板串联起来就行了。”

他们的谈话引起了六花的注意。感到奇怪的她决定跟随他们。但在那之前，她需要战胜心中的恶魔。

六花初始的攻击力 $A$ 和攻击力增量 $D$ 均为 $0$。总共有 $n$ 个回合。对于 $i = 1, 2, \dots, n$，在第 $i$ 回合开始时，六花的攻击力 $A$ 会增加 $D$，然后她可以执行以下操作之一：

1. 进行攻击，造成 $(A + a_i)$ 的伤害。
2. 使用 LCR 的“全能花环”（Omnipotent Garland）将增量 $D$ 增加 $b_i$。
3. 使用她的“Schwarz Sechs Prototype Mark II”将攻击力 $A$ 增加 $c_i$。

六花想知道她总共能造成的最大伤害是多少。你能帮帮她吗？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。接下来是 $T$ 个测试用例。 每个测试用例的输入格式如下： 第一行包含一个整数 $n$ ($1 \le n \le 100$)，表示回合数。 接下来的 $n$ 行包含 $i = 1, 2, \dots, n$ 时的 $\{a_i\}, \{b_i\}, \{c_i\}$。其中第 $i$ 行包含三个整数 $a_i, b_i, c_i$ ($1 \le a_i, b_i, c_i \le 10^9$)，按顺序由空格分隔。

保证所有测试用例中 $n$ 的总和不超过 $100$。

输出格式

输出 $T$ 行；每行包含一个整数，即该测试用例的答案。

样例

输入 1

3
2
3 1 2
3 1 2
3
3 1 2
3 1 2
3 1 2
5
3 1 2
3 1 2
3 1 2
3 1 2
3 1 2

输出 1

6
10
24