题目描述

小 H 在这一年里刷了很多的算法题，但是他一点也不快乐。在一个偶然的一天，他发现了一个能够让他快乐的刷题方式。

小 H 只会在 $3$ 个平台上刷题，分别是 ZOJ，POJ，CF，某一天在某个平台上刷题时他获得的快乐值为：$Z_i,P_i,C_i$ ，他每天只能选一个平台刷题并且获得这个平台的快乐值。小 H 想知道在 $n$ 天的时间里，他能获得的最大的快乐值是多少。注意，他不想连续两天刷同一个平台上的题。

输入格式

第一行一个正整数 $T$（$1\le T \le 100$），代表测试样例的组数。

每个测试样例的第一行输入 $1$ 个正整数 $n$（$1\le n\le 2\times10^5$），代表小 H 要刷题的天数。

接下来的 $n$ 行，每行 $3$ 个正整数 $Z_i,P_i,C_i$（$1\le Z_i,P_i,C_i\le10^5$），代表他在ZOJ，POJ，CF，上刷题时获得的快乐值。

数据保证 $\sum n \le 2\times 10^5$。

输出格式

输出 $T$ 行，每行一个正整数表示小 H 能获得的最大快乐值。

输入样例

2
3
10 2 8
3 5 9
8 1 10
2
1 2 3
4 5 6

输出样例

27
8

提示

对于样例 $1$：

小 H 第 $1$ 天选择 ZOJ，第 $2$ 天选择 CF，第 $3$ 天选择 ZOJ，他获得的最大快乐值为 $27$。

对于样例 $2$：

小 H 第 $1$ 天选择 CF，第 $2$ 天选择 POJ，他获得的最大快乐值为 $8$。