B 禁忌的联盟 (lol)

题目描述

在遥远的尤里安大陆上，流传着一种古老的召唤术。召唤师通过排列不同的「符石」组成法阵，召唤出强大的魔灵。

每块符石都有两个属性：

• 「源印」编号 $a_i$：表示它的魔源流派；
• 「能核」值 $b_i$：决定它与其他符石的共鸣能力。

要组成一个强大且稳定的召唤链，必须满足两条禁忌规则：

1. 相邻的符石 源印不同，即相邻的 $a_i$ 不相等，用数学表达式表示为 $a_i \neq a_{i + 1}$；
2. 相邻的符石 能核共鸣，即相邻的 $b_i$ 与 $b_j$ 满足 $\gcd(b_i, b_j) > 1$，其中 $\gcd$ 表示最大公约数。

你手中有 $n$ 块符石。请你选择一组符石，构成一个合法的子序列（不要求连续），使得满足上述规则的前提下，召唤链的长度最大。

请你计算并输出该最大长度。

输入格式

• 第一行一个整数 $n$，表示符石数量。
• 接下来 $n$ 行，每行两个整数 $a_i$，$b_i$（$1 \leq a_i, b_i \leq 10^5$），表示第 $i$ 块符石的源印与能核值。

输出格式

输出一个整数，表示最大合法子序列的长度。

样例

样例输入 1

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

样例输出 1

7

样例输入 2

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

样例输出 2

5  

数据范围与约定

对于所有测试数据中，满足：

• $1 \leq n \leq 2 \times 10^5$；

• 对于所有 $a_i$，$b_i$，有 $1 \leq a_i, b_i \leq 10^5$。