D. Зигзаги
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив $$$a_1, a_2 \dots a_n$$$. Посчитайте количество таких четверок $$$(i, j, k, l)$$$, что:

  • $$$1 \le i < j < k < l \le n$$$;
  • $$$a_i = a_k$$$ и $$$a_j = a_l$$$;
Входные данные

В первой строке задано единственное целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных.

В первой строке каждого набора входных данных задано единственное целое число $$$n$$$ ($$$4 \le n \le 3000$$$) — размер массива $$$a$$$.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) — сам массив $$$a$$$.

Гарантируется, что сумма $$$n$$$ в одном тесте не превосходит $$$3000$$$.

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

Для каждого набора входных данных, выведите количество описанных четверок.

Пример
Входные данные
2
5
2 2 2 2 2
6
1 3 3 1 2 3
Выходные данные
5
2
Примечание

В первом наборе входных данных, каждая четверка индексов $$$i < j < k < l$$$ подходит, а потому ответ — это количество четверок.

Во втором наборе, есть только $$$2$$$ подходящих четверки:

  • $$$(1, 2, 4, 6)$$$: $$$a_1 = a_4$$$ и $$$a_2 = a_6$$$;
  • $$$(1, 3, 4, 6)$$$: $$$a_1 = a_4$$$ и $$$a_3 = a_6$$$.