SCNU 展开了一次集训，一共 $n$ 天，lre 也参加了这场集训，lre 喜欢 $3$ 个 OJ，所以只会在这三个 OJ 上面做题，这三个 OJ 是 ZOJ,POJ,CF。

lre 每天 AC 恰好一道题目，每 AC 一道题目，他都能得到一些快乐值。对于第 $i$ 天 $(1 ≤ i ≤ n)$，lre 可以选择一个 OJ，并且 AC 里面的一道题目。

• 选择 ZOJ，他将得到 $Z_i$ 的快乐值
• 选择 POJ，他将得到 $P_i$ 的快乐值。
• 选择 CF，他将得到 $C_i$ 的快乐值。

但是，lre 绝对不会连续两天在同一个 OJ 做题，他觉得这样太枯燥了。请问，第 $n$ 天结束后，lre 最多能获得多少快乐值?

第一行有一个数 $T (1 ≤ T ≤ 100000)$

每组第一行包含一个数 $n$，表示集训有 $n$ 天。$(1 ≤ n ≤ 1000000)$

接下来有 $n$ 行，每行有三个数 $Z_i ,P_i ,C_i$。$(1 ≤ Z_i ,P_i ,C_i ≤ 100)$

数据保证各组的 $n$ 之和不会超过 $1000000$。

对于每组测试，输出一行，表示答案。