计数押韵

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定整数数组 $a_1,a_2,\ldots,a_n$。若一对下标 $(i,j)$（$i<j$）不存在任何数组中的元素 $a_k$，使得 $a_k$ 同时整除 $a_i$ 与 $a_j$，则称它为好对。求好对数量。

输入格式

第一行包含测试组数 $t$。每组第一行包含 $n$，第二行包含 $n$ 个整数 $a_i$。

输出格式

每组输出一个整数，表示好对数量。

样例输入 1

6
4
2 4 4 4
4
2 3 4 4
9
6 8 9 4 6 8 9 4 9
9
7 7 4 4 9 9 6 2 9
18
10 18 18 15 14 4 5 6 8 9 10 12 15 16 18 17 13 11
21
12 19 19 18 18 12 2 18 19 12 12 3 12 12 12 18 19 16 18 19 12

样例输出 1

0
3
26
26
124
82

数据范围

• $1\le t\le2\cdot10^4$，$1\le n\le10^6$；
• $1\le a_i\le n$；
• 所有测试组的 $n$ 之和不超过 $10^6$。