题目描述

给定一个长为 $n$ 的序列 $\{a_i\}$，求有多少个数对 $(i, j)$，满足 $1 \le i < j \le n$ 且 $a_i \cdot a_j$ 能被 $i \cdot j$ 整除。

输入格式

第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 次询问，每次询问包含两行。

第一行一个正整数 $n$。

第二行 $n$ 个正整数 $a_i$。

输出格式

共 $T$ 行，每行一个整数，表示符合条件的数对个数。

3
3
1 2 3
4
2 3 5 6
5
3 6 9 10 14

3
2
4

数据范围

• 对于 $30\%$ 的数据，$1 \le T \le 5$，$1 \le n \le 10^3$；
• 对于另外 $30\%$ 的数据，$1 \le a_i \le 20$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^4$，$2 \le n, \sum n \le 10^5$，$1 \le a_i \le 10^5$。