题目描述

为了生产雪人，工厂准备了三条循环传送带，每条传送带上都有 $n$ 个雪球（位置按顺序循环），三条传送带分别用于头、身体、腿。 第一条传送带上的球大小依次为 $a_1,a_2,\dots,a_n$；第二条为 $b_1,b_2,\dots,b_n$；第三条为 $c_1,c_2,\dots,c_n$。由于传送带是循环的，我们把下标看作模 $n$ 的（例如位置 $i+n$ 与位置 $i$ 是相同的球）。

每个雪人由三颗球组成，要求头 $<$ 身体 $<$ 腿（即若头、身体、腿的大小分别为 $x,y,z$，则必须满足 $x<y<z$）。生产程序如下：先选定三个起始下标 $i,j,k$（$1\le i,j,k\le n$），然后按顺序组装 $n$ 个雪人：

• 第 $1$ 个雪人用球 $(a_i,b_j,c_k)$；
• 第 $2$ 个雪人用球 $(a_{i+1},b_{j+1},c_{k+1})$；
• $\dots$
• 第 $n$ 个雪人用球 $(a_{i+n-1},b_{j+n-1},c_{k+n-1})$；

这里的下标均按循环（模 $n$）处理。要求所选的 $i,j,k$ 能保证 对所有这 $n$ 个雪人都满足 稳定条件 $a_{i+t}<b_{j+t}<c_{k+t}$（对所有 $t=0,1,\dots,n-1$）。

请你统计满足条件的三元组 $(i,j,k)$ 的数量。

输入格式

• 第一行包含一个整数 $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$。

输出格式

对于每个测试用例，输出一行，包含一个整数——满足条件的 $(i,j,k)$ 三元组数量。

样例输入

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

样例输出

4
27
0
10

说明

样例解释

• 第一个测试例（$n=2$）： 满足条件的 $(i,j,k)$ 有 $4$ 种，如题面示例所列。
• 第二个测试例中任意 $(i,j,k)$ 都满足条件，因此共有 $n^3=27$ 种组合。
• 第三个测试例任何选择都会出现 $b$ 与 $a$ 相等的情况，所以没有合法三元组。
• 第四个测试例共有 $10$ 种合法选择。