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

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

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

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.