Warm sunshine, cool wind and a fine day, while the girl watching is pursuing in chaos. Rikka reached out her hand and got the garland on her head, finding LCR with the immortal smile. The dream ended up waking, but the doubts will never disappear. In the end, without knowing about LCR, Rikka was invited to Shuyuan Men, a street of Chinese traditional arts in Xi'an.
``Is it enough to use the stored wires?''
``No problem... Those leaders are only concerned about expanding EC Final for the school's and their `achievements'. All chores are ours. It is fine to simply connect those wiring boards in the series for each row.''
Their conversation engaged Rikka. Feeling strange, she decided to follow them. But before all, she needs to beat the devil in her heart.
Rikka has an aggressivity A and an increment D of it, which are both 0 initially. There are n rounds in total. For , at the beginning of i-th round Rikka's aggressivity A increases by the increment D, and then she can do one of the following:

    ·Attack and cause a damage of .
    ·Use the Omnipotent Garland from LCR to increase the increment D by .
    ·Use her Schwarz Sechs Prototype Mark II to increase the aggressivity A by .

Rikka wonders the maximal possible damage she could cause in total. Could you help her?

The first line contains a single integer , the number of test cases. Then T test cases follow.
The input format of each test case is as follows:
The first line contains a single integer , the number of rounds.
The following n lines contain  for . The i-th line among them contains three integers  separated by spaces in order.
It is guaranteed that the sum of n in all test cases is at most 100.

Output T lines; each line contains one integer, the answer to that test case.

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