D. Coconuting
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mouf, a little penguin from Aleppo, dreamed of sunny beaches and coconuts. One day, his penguin companions created a challenge for him to unravel, with a ticket to their island awaiting as the reward.

Mouf was given an array of integers $$$a$$$ of length $$$n$$$. Mouf's companions consider a pair of indices $$$\langle i, j \rangle$$$ $$$(1 \le i \lt j \le n)$$$ $$$\it{coconut}$$$ if there exists positive integers $$$x$$$ and $$$y$$$ such that:

  • $$$a_i = \dfrac{x^2}{y}$$$;
  • $$$a_j = \dfrac{y^2}{x}$$$.

Help Mouf find the number of $$$\it{coconut}$$$ pairs in the array $$$a$$$ to win a trip to the magical island and enjoy sunny days and coconut feasts with his companions.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 5 \cdot 10^4)$$$ — the length of the array $$$a$$$.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the elements of the array $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^4$$$.

Output

For each test case, output a single integer — the number of $$$\it{coconut}$$$ pairs in the array $$$a$$$.

Example
Input
3
2
1 1
5
2 3 2 3 2
8
2 2 2 2 4 4 8 16
Output
1
4
11