Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

G1. Permutation Problem (Simple Version)
time limit per test
3 seconds
memory limit per test
128 megabytes
input
standard input
output
standard output

This is a simple version of the problem. The only difference is that in this version n≤105 and the sum of n for all sets of input data does not exceed 105.

You are given a permutation p of length n. Calculate the number of index pairs 1≤i<j≤n such that pi⋅pj is divisible by i⋅j without remainder.

A permutation is a sequence of n integers, where each integer from 1 to n occurs exactly once. For example, [1], [3,5,2,1,4], [1,3,2] are permutations, while [2,3,2], [4,3,1], [0] are not.

Input

Each test consists of multiple sets of input data. The first line contains a single integer t (1≤t≤104) — the number of sets of input data. Then follows their description.

The first line of each set of input data contains a single integer n (1≤n≤105) — the length of the permutation p.

The second line of each set of input data contains n distinct integers p1,p2,…,pn (1≤pi≤n) — the permutation p.

It is guaranteed that the sum of n for all sets of input data does not exceed 105.

Output

For each set of input data, output the number of index pairs 1≤i<j≤n such that pi⋅pj is divisible by i⋅j without remainder.

Example
Input
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
Output
0
1
1
3
9
3
Note

In the first set of input data, there are no index pairs, as the size of the permutation is 1.

In the second set of input data, there is one index pair (1,2) and it is valid.

In the third set of input data, the index pair (1,2) is valid.

In the fourth set of input data, the index pairs (1,2), (1,5), and (2,5) are valid.