出题人太菜，暂无测试数据。

题目描述

给定一张包含 \(n\) 个点的有向无环图，点的编号从 \(1\) 到 \(n\)。

• 对于所有 \(1 \leq i \leq n-1\)，存在一条从 \(i\) 到 \(i+1\) 的长度为 \(a_i\) 的有向边。
• 对于所有 \(1 \leq i \leq n-2\)，存在一条从 \(i\) 到 \(i+2\) 的长度为 \(b_i\) 的有向边。
• 对于所有 \(1 \leq i \leq n-3\)，存在一条从 \(i\) 到 \(i+3\) 的长度为 \(c_i\) 的有向边。

现在，定义 \(d(s, t)\) 表示从点 \(s\) 到点 \(t\) 的最短路径。你的任务是求出所有可能的 \(d(s, t)\) 之和。

输入输出格式

输入格式

第一行一个正整数 \(T\),表示测试数据组数。

每组测试数据第一行一个正整数 \(n\)。

第二行 \(n-1\) 个整数 \(a_i\).

第三行 \(n-2\) 个整数 \(b_i\).

第四行 \(n-3\) 个整数 \(c_i\).

输出格式

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

样例

输入

2
4
1 1 1
1 1
1
5
1 2 3 4
2 3 4
3 4

输出

6
31

数据范围

本题共有\(5\)个测试点，每个\(20\)分。

测试点编号	\( n\)	\(\sum n\)	特殊性质
\(1\)	\(\le 1000\)	\(\le 10000\)	无
\(2\)	\(\le 20000\)	\(\le 10^5\)	\(b_i=a_i+a_{i+1},c_i=a_i+a_{i+1}+a_{i+2}\)
\(3\)	\(\le 50000\)	\(\le 10^5\)	\(c_i=a_i+a_{i+1}+a_{i+2}\)
\(4\)	\(\le 70000\)	\(\le 1.5\times 10^5\)	无
\(5\)	\(\le 10^5\)	\(\le 3\times 10^5\)	无

对于所有测试数据，\(1\le n\le 10^5,1\le a_i,b_i,c_i\le 10^4,\sum n\le 3\times 10^5,1\le T\le 10^4\)