问题背景

我常常追忆过去。

生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。

云朵之间亦有分别：积云厚重，而卷云飘淼。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。

追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。

过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。

我该在哪里停留？我问我自己。

问题描述

珂朵莉给了你一个长度为 $n$ 的正整数数列 $a$ 和一个 $1$ 到 $n$ 的排列 $p$， 请计算满足以下条件的整数对 $(i, j)$ 的数量：

• $1 \le i \lt j \le n$
• $p[i] \lt p[j]$
• 令 $\mathrm{lpf}(x)$ 表示 $x$ 的最大质因数（largest prime factor），则 $\mathrm{lpf}(a[i] + a[j]) \mid \gcd(i, j)$
  提示：$A \mid B$ 表示 $B$ 能被 $A$ 整除

输入格式

第一行包含一个整数 $n$。 ($2 \le n \le 2 \times 10^5$)
第二行包含 $n$ 个整数 $a[1], a[2], \dots, a[n]$。 ($1 \le a[i] \le 2 \times 10^5$)
第三行包含 $n$ 个整数 $p[1], p[2], \dots, p[n]$，保证是 $1$ 到 $n$ 的一个排列。

输出格式

输出一个整数，表示满足条件的整数对数量。