给定一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。
一对整数 $$$(i, j)$$$,使得 $$$1 \le i < j \le n$$$ 被称为好,如果不存在整数 $$$k$$$ ($$$1 \le k \le n$$$) 使得 $$$a_i$$$ 可以被 $$$a_k$$$ 整除并且 $$$a_j$$$ 是可同时被 $$$a_k$$$ 整除。
请找出好对的数量。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。
输出
对于每个测试用例,输出良好对的数量。
示例
输入 #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, 2)$$$、$$$(2, 3)$$$ 和 $$$(2, 4)$$$。