CF2182C.Production of Snowmen

To create a truly festive atmosphere, Santa's helpers have opened a factory for producing snowmen!

Each snowman consists of three snowballs — a head, a torso, and legs. For the snowman to be stable, the ball forming the legs must be strictly larger than the ball forming the torso; in turn, the ball forming the torso must be strictly larger than the ball forming the head. Formally, if we denote the sizes of the head, torso, and legs as $a, b, c$ respectively, the snowman will be stable if and only if $a \lt b \lt c$.

At the snowman production factory, there are three conveyors, each containing $n$ snowballs. The first conveyor contains balls of sizes $a_1, a_2, \dots, a_n$; the second contains balls of sizes $b_1, b_2, \dots, b_n$; the third contains balls of sizes $c_1, c_2, \dots, c_n$. The conveyors are cyclic; in other words, after the element numbered $n$, the element numbered $1$ follows again, and we can consider that the ball numbered $i$ and the ball numbered $i+n$ (as well as the ball numbered $i+2n$, $i+3n$, and so on) are the same ball.

To produce snowmen, it is necessary to specify three parameters $i, j, k$ ($1 \le i, j, k \le n$), indicating which balls on each conveyor the production starts from. After that, the snowmen will be assembled from the balls as follows:

• the first snowman will have a head of size $a_i$, a torso of size $b_j$, and legs of size $c_k$;
• the second snowman will have a head of size $a_{i+1}$, a torso of size $b_{j+1}$, and legs of size $c_{k+1}$;
• and so on;
• the $n$-th (last) snowman will have a head of size $a_{i+n-1}$, a torso of size $b_{j+n-1}$, and legs of size $c_{k+n-1}$.

The parameters $i, j, k$ must be chosen in such a way that all $n$ snowmen are stable. Your task is to count the number of suitable combinations of parameters.

为了营造真正的节日氛围，圣诞老人的助手们开设了一家雪人制造工厂！

每个雪人由三个雪球组成——一个头部、一个躯干和一对腿部。为了让雪人保持稳定，构成腿部的雪球尺寸必须严格大于构成躯干的雪球；而构成躯干的雪球尺寸又必须严格大于构成头部的雪球。形式化地，若我们分别用 $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$ 个雪人均稳定。你的任务是计算满足条件的参数组合 $(i,j,k)$ 的总数。

The first line contains one integer $t$ ($1 \le t \le 5000$) — the number of test cases.

Each test case consists of four lines:

• the first line contains one integer $n$ ($1 \le n \le 5000$);
• the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 3n$);
• the third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 3n$);
• the fourth line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 3n$).

Additional constraint on the input: the sum of $n$ across all test cases does not exceed $5000$.

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

For each test case, output one integer — the number of combinations of parameters $i, j, k$ for which all $n$ snowmen will be stable.

对于每个测试用例，输出一个整数——满足所有 $n$ 个雪人均为稳定状态的参数组合 $i, j, k$ 的数量。

In the first example, suitable sets of parameters $i, j, k$ are as follows:

• $i = 1, j = 1, k = 2$: then the snowmen will be $(1, 3, 4)$ and $(2, 4, 5)$;
• $i = 1, j = 2, k = 1$: then the snowmen will be $(1, 4, 5)$ and $(2, 3, 4)$;
• $i = 2, j = 1, k = 2$: then the snowmen will be $(2, 3, 4)$ and $(1, 4, 5)$;
• $i = 2, j = 2, k = 1$: then the snowmen will be $(2, 4, 5)$ and $(1, 3, 4)$.

In the second example, all combinations of parameters are suitable.

In the third example, for any combination of parameters, a snowman with a head size of $2$ and a torso size of $2$ will be produced, which is not stable.

在第一个例子中，合适的参数组 $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$ 的雪人，该雪人不稳定。