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。

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