为了营造真正的节日气氛,圣诞老人的帮手们开设了一家生产雪人的工厂!
每个雪人都由三个雪球组成——头部、躯干和腿。为了使雪人保持稳定,形成腿部的球必须严格大于形成躯干的球;反过来,形成躯干的球必须严格大于形成头部的球。形式上,如果我们将头部、躯干和腿的尺寸分别表示为$$$a、b、c$$$,则当且仅当$$$a \lt b \lt c$$$ 时,雪人才是稳定的。
在雪人生产工厂,有三个传送带,每个传送带包含$$$n$$$个雪球。第一个传送带包含尺寸为 $$$a_1, a_2, \dots, a_n$$$ 的球;第二个包含尺寸为 $$$b_1, b_2, \dots, b_n$$$ 的球;第三个包含尺寸为 $$$c_1、c_2、\dots、c_n$$$ 的球。输送机是循环式的;换句话说,在编号为$$$n$$$的元素之后,又跟着编号为$$$1$$$的元素,我们可以认为编号为$$$i$$$的球和编号为$$$i+n$$$的球(以及编号为$$$i+2n$$$、$$$i+3n$$$的球等)是同一个球。
要生产雪人,需要指定三个参数 $$$i, j, k$$$ ($$$1 \le i, j, k \le n$$$),表示从每个传送带上的哪些球开始生产。之后,雪人将由球组装而成,如下所示:
- 第一个雪人的头部尺寸为$$$a_i$$$,躯干尺寸为$$$b_j$$$,腿尺寸为$$$c_k$$$;
- 第二个雪人的头部尺寸为$$$a_{i+1}$$$,躯干尺寸为$$$b_{j+1}$$$,腿尺寸为$$$c_{k+1}$$$;
- 等等;
- 第$$$n$$$(最后一个)雪人的头部尺寸为$$$a_{i+n-1}$$$,躯干尺寸为$$$b_{j+n-1}$$$,腿尺寸为$$$c_{k+n-1}$$$。
参数 $$$i、j、k$$$ 的选择必须确保所有 $$$n$$$ 雪人都是稳定的。您的任务是计算合适的参数组合的数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。
每个测试用例由四行组成:
- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 3n$$$);
- 第三行包含$$$n$$$整数$$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 3n$$$);
- 第四行包含$$$n$$$整数$$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 3n$$$)。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$5000$$$。
输出
对于每个测试用例,输出一个整数 - 所有 $$$n$$$ 雪人都稳定的参数 $$$i, j, k$$$ 的组合数量。
示例
输入复制
421 23 45 431 1 12 2 23 3 341 2 1 23 3 2 25 5 5 551 4 2 3 56 4 5 7 67 5 8 10 10
输出复制
427010
注意
在第一个示例中,合适的参数集 $$$i, j, k$$$ 如下:
- $$$i = 1, j = 1, k = 2$$$:那么雪人将是 $$$(1, 3, 4)$$$ 和 $$$(2, 4, 5)$$$;
- $$$i = 1, j = 2, k = 1$$$: 那么雪人将是 $$$(1, 4, 5)$$$ 和 $$$(2, 3, 4)$$$;
- $$$i = 2, j = 1, k = 2$$$:那么雪人将是 $$$(2, 3, 4)$$$ 和 $$$(1, 4, 5)$$$;
- $$$i = 2, j = 2, k = 1$$$:那么雪人将是 $$$(2, 4, 5)$$$ 和 $$$(1, 3, 4)$$$。
在第二个示例中,所有参数组合都是合适的。
在第三个例子中,对于任何参数组合,都会产生一个头部尺寸为$$$2$$$、躯干尺寸为$$$2$$$的雪人,这是不稳定的。