A141176.午枫的航海日志

午枫在破译宝箱密码时，发现了一张古老的航海日志，上面记录了一串神秘的数字序列 $a_1, a_2, \ldots, a_n$。

经过研究，他意识到，如果在这个序列中存在一个子序列（不要求连续）恰好形如：

$$p,\ 0,\ p,\ q$$

其中 $p$ 和 $q$ 都是 正整数，那么这个子序列就对应着一组有效的航海坐标参数 $(p, q)$。

现在，午枫想知道，对于给定的序列，一共有多少组不同的 正整数 数对 $(p, q)$，使得序列中存在这样的子序列。

注意：同一个 $(p, q)$ 只计一次，不管它在序列中出现多少次。

本题包含多组测试数据。

第一行一个正整数 $T$（$1 \le T \le 20$），表示数据组数。

对于每组数据：

• 第一行一个正整数 $n$（$4 \le n \le 10^6$），表示序列长度。
• 第二行 $n$ 个自然数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^6$），表示神秘数字序列。

保证全部数据中，只有最多 $10$ 组数据的 $n > 10^5$。

对于每组数据，输出一行一个自然数，表示符合条件的 $(p, q)$ 数对个数。

数据范围

• $1 \le T \le 20$
• $4 \le n \le 10^6$
• $0 \le a_i \le 10^6$
• 只有最多 $10$ 组数据的 $n > 10^5$