C. Производство снеговиков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы создать по-настоящему новогоднюю атмосферу, помощники Деда Мороза открыли фабрику по производству снеговиков!

Каждый снеговик состоит из трех снежных шаров — головы, туловища и ног. Чтобы снеговик был устойчивым, шар, образующий ноги снеговика, должен быть строго больше шара, образующего туловище; в свою очередь, шар, образующий туловище, должен быть строго больше шара, образующего голову. Формально, если обозначить размеры головы, туловища и ног за $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число — количество комбинаций параметров $$$i, j, k$$$, при которых все $$$n$$$ снеговиков будут устойчивыми.

Пример
Входные данные
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
Примечание

В первом примере подходящие наборы параметров $$$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$$$, а он не является устойчивым.