G1. 排列问题（简单版）

• 时间限制：每个测试点 $3$ 秒
• 内存限制：每个测试点 $128$ 兆字节

这是该问题的简单版本。唯一的区别在于，此版本中 $n \le 10^5$ 且所有输入数据组的 $n$ 之和不超过 $10^5$。

给你一个长度为 $n$ 的排列 $p$。计算满足 $p_i \cdot p_j$ 能被 $i \cdot j$ 整除的无序对 $(i, j)$（$1 \le i < j \le n$）的数量。

排列是一个长度为 $n$ 的序列，其中 $1$ 到 $n$ 的每个整数恰好出现一次。例如，$[1]$、$[3,5,2,1,4]$、$[1,3,2]$ 是排列，而 $[2,3,2]$、$[4,3,1]$、$[0]$ 不是。

输入

每个测试包含多组输入数据。第一行包含一个整数 $t$（$1 \le t \le 10^4$）——输入数据组的数量。接下来是每组数据的描述。

每组数据的第一行包含一个整数 $n$（$1 \le n \le 10^5$）——排列 $p$ 的长度。

每组数据的第二行包含 $n$ 个互不相同的整数 $p_1, p_2, \dots, p_n$（$1 \le p_i \le n$）——排列 $p$。

保证所有输入数据组的 $n$ 之和不超过 $10^5$。

输出

对于每组输入数据，输出一个整数，表示满足条件的下标对的数量。

示例

输入

6
1
1
2
1 2
3
2 3 1
5
2 4 1 3 5
12
8 9 7 12 1 10 6 3 2 4 11 5
15
1 2 4 6 8 10 12 14 3 9 15 5 7 11 13

输出

0
1
1
3
9
3

注

• 在第一组数据中，排列长度为 $1$，没有下标对，因此答案为 $0$。
• 在第二组数据中，存在一个下标对 $(1,2)$ 且满足条件。
• 在第三组数据中，下标对 $(1,2)$ 满足条件。
• 在第四组数据中，满足条件的下标对为 $(1,2)$、$(1,5)$ 和 $(2,5)$。