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.

Input

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$$$.

Output

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

Note

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.

Production of Snowmen

Examples