Description

你现在正在打一个boss，一共n个回合。你有一个攻击值A和一个增量D，初始均为0。在第i回合，回合初，攻击值A 将会自动增加D，然后你选择以下三个决策之一：

1. 发动攻击，造成伤害为(A+ai)
2. 增加增量D，使之变为(D+bi)
3. 增加攻击值A，使之变为(A+ci)

给出上述信息，请问你能造成的最大伤害是？

Input

一行一个正整数T(1≤T≤10)，共有 T组测试数据，每组输入格式为：

一行一个正整数n(1≤n≤100)，表示回合数

接下来n 行，每行三个非负整数ai,bi,ci ( 0≤ai, bi, ci≤10^9 )，含义见上

Output

T行，每行一个数表示答案

Samples

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

6  
10  
24

输入 #2 见数据包

输出 #2 见数据包

样例解释

样例 #1

每组数据一种可能的解：（这里我们用n个数字（1/2/3）依次表示n 个回合每回合的决策）

第一组数据：1,1

第二组数据：3,1,1

第三组数据：2,3,1,1,1

Limitation