B. Киа, Кио и числа-квадраты
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Киа и Кио провели лето в порту Мехрагана, где на утёсах у тёмного моря стоят $$$n$$$ маяков.

Маяки Мехрагана не светят. Каждую ночь на каждом из них огнём записывается число, и моряки прокладывают путь по этим числам.

Закон маяков таков: если сегодня ночью маяк показывает $$$x$$$, то следующей ночью он показывает сумму квадратов десятичных цифр числа $$$x$$$.

Например, маяк, показывающий $$$23$$$, следующей ночью покажет $$$2^2+3^2=13$$$, затем $$$1^2+3^2=10$$$, а затем $$$1$$$.

В ночь $$$0$$$ сезона маяк $$$i$$$ показывает число $$$a_i$$$. Начиная с этой ночи, закон применяется один раз за ночь вечно.

Кио называет два маяка $$$i$$$ и $$$j$$$ синхронными, если существует такая ночь, после которой они всегда показывают одно и то же число в каждую ночь.

Киа спрашивает: сколько пар $$$(i, j)$$$, где $$$i \lt j$$$, являются синхронными?

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

Каждый тест содержит несколько наборов входных данных. В первой строке содержится количество наборов входных данных $$$t$$$ ($$$1 \le t \le 1000$$$). Далее следует описание наборов входных данных.

Каждый набор входных данных состоит из двух строк.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 1000$$$) — количество маяков.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — числа, которые маяки показывают в ночь $$$0$$$.

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

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

Для каждого набора входных данных выведите одно целое число — количество пар $$$(i, j)$$$, где $$$i \lt j$$$, для которых маяки $$$i$$$ и $$$j$$$ синхронны.

Пример
Входные данные
4
5
7 4 16 4 2
4
1 7 10 100
3
4 16 37
3
2 20 4
Выходные данные
1
6
0
1
Примечание

В первом наборе входных данных:

  • Маяк $$$1$$$ начинает с числа $$$7$$$: $$$7 \to 49 \to 97 \to 130 \to 10 \to 1$$$, после чего навсегда остаётся на числе $$$1$$$.
  • Маяки $$$2$$$ и $$$4$$$ начинают с числа $$$4$$$, поэтому каждую ночь показываемые ими числа совпадают.
  • Маяк $$$3$$$ начинает с числа $$$16$$$, а маяк $$$5$$$ — с числа $$$2$$$; каждый из них находится в своей точке цикла, который обнаружил Кио, и никогда ни с кем не совпадает.

Таким образом, единственная синхронная пара — $$$(2, 4)$$$, и ответ равен $$$1$$$.

Во втором наборе входных данных каждый маяк рано или поздно достигает числа $$$1$$$ и навсегда остаётся на нём, поэтому все маяки попарно синхронны, что даёт $$$6$$$ пар.

В четвёртом наборе входных данных в ночь $$$1$$$ маяк $$$2$$$ показывает $$$2^2+0^2 = 4$$$, а маяк $$$1$$$ показывает $$$2^2 = 4$$$. Начиная с ночи $$$1$$$ они навсегда совпадают. Маяк $$$3$$$ начинает с числа $$$4$$$, поэтому он на одну ночь опережает их обоих и не синхронен ни с одним из них.