← 返回题目列表

Codeforces · 1884/D

D. 数韵

中文机器翻译题面 查看原题

给定一个整数数组 $$$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)$$$。