Kia and Kio spent the summer at the port of Mehragan, where $n$ lighthouses stand on the cliffs facing the dark sea.

The lighthouses of Mehragan do not give light. Every night a number is written in fire on each of them, and the sailors read their way from those numbers.

The law of the lighthouses is this: if a lighthouse shows $x$ tonight, then tomorrow night it shows the sum of the squares of the decimal digits of $x$.

For example, a lighthouse showing $23$ will show $2^2+3^2=13$ tomorrow, then $1^2+3^2=10$, and then $1$.

On night $0$ of the season, lighthouse $i$ shows the number $a_i$. From that night on, the law is applied once every night, forever.

Kio calls two lighthouses $i$ and $j$ in tune if there exists a night after which, forever, both of them show exactly the same number on every single night.

Kia asks: how many pairs $(i, j)$ with $i \lt j$ are in tune?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 1000$). The description of the test cases follows.

Each test case consists of two lines.

The first line of each test case contains a single integer $n$ ($1 \le n \le 1000$) — the number of lighthouses.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the number shown by each lighthouse on night $0$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

Output

For each test case, print a single integer — the number of pairs $(i, j)$ with $i \lt j$ such that lighthouses $i$ and $j$ are in tune.

Note

In the first test case:

• Lighthouse $1$ starts at $7$: $7 \to 49 \to 97 \to 130 \to 10 \to 1$, and it stays at $1$ forever.
• Lighthouses $2$ and $4$ both start at $4$, so they show the same number on every night.
• Lighthouse $3$ starts at $16$ and lighthouse $5$ starts at $2$; each of them is at a different point of the cycle Kio found, and never matches anybody.

So the only pair in tune is $(2, 4)$, and the answer is $1$.

In the second test case, every lighthouse sooner or later reaches $1$ and stays there, so all of them are pairwise in tune, which gives $6$ pairs.

In the fourth test case, on night $1$, lighthouse $2$ shows $2^2+0^2 = 4$, and lighthouse $1$ shows $2^2 = 4$. From night $1$ on, they are identical forever. Lighthouse $3$ starts at $4$, so it is one night ahead of both of them and is in tune with neither.