时间限制：1000 ms　内存限制：1024 MiB

题目描述

给定一个 $1$ 到 $N$ 的整数的排列 $P=(P_1,P_2,\ldots,P_N)$。

请你计算满足 $1\leq i\leq j\leq N$，且同时满足 $\gcd(i,j)\neq 1$ 且 $\gcd(P_i,P_j)\neq 1$ 的整数对 $(i,j)$ 的个数。

其中，对于正整数 $x,y$，$\gcd(x,y)$ 表示 $x$ 和 $y$ 的最大公约数。

输入格式

格式如下：

$N$

$P_1\ \ P_2\ \ \ldots\ \ P_N$

输出格式

输出答案。

样例

输入 #1

6
5 1 3 2 4 6

输出 #1

6

输入 #2

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

输出 #2

32

说明/提示

限制条件

• $1 \leq N \leq 2\times 10^5$

• $(P_1,P_2,\ldots,P_N)$ 是 $(1,2,\ldots,N)$ 的一个排列。

• 输入均为整数。

样例解释 1

满足条件的组有 $(3,3)$、$(3,6)$、$(4,4)$、$(4,6)$、$(5,5)$、$(6,6)$ 共 $6$ 个。因此，输出 $6$。

数据范围