One day, Little L went to the suburbs and discovered a new species of fireflies. They are colorful and have varying brightness, and they like to perch in a row along the roadside. Little L has his eyes on them and wants to catch some of them.

There are $n$ fireflies in a row along the roadside. The $i$-th firefly has a brightness of $w_i$ and a color of $c_i$. Little L wants to catch some of them (not necessarily contiguous) and arrange them in a row in the same relative order as they appeared on the roadside. The final sequence of fireflies must satisfy:

1. Adjacent fireflies must have different colors.
2. Adjacent fireflies must have brightness values that are not coprime (i.e., their greatest common divisor is greater than 1).

Now, Little L wants to know the maximum number of fireflies he can catch. Can you help him?

Input

Each test file contains only one set of test data.

The first line contains an integer $n$ ($1 \le n \le 5 \times 10^5$), representing the number of fireflies.

The second line contains $n$ positive integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 5 \times 10^5$), representing the brightness of the $i$-th firefly.

The third line contains $n$ positive integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 5 \times 10^5$), representing the color of the $i$-th firefly.

Output

Output a single integer representing the maximum number of fireflies Little L can catch.

Examples

Input 1

6
6 6 6 6 6 6
1 1 2 2 3 3

Output 1

3

Input 2

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

Output 2

7

备注

在样例的第一组测试数据中：所有萤火虫的亮度都是一样的，任意的方案都满足”不互质”的要求。要使相邻萤火虫的颜色不同，一种最优的方案是选择第 1, 3, 5 只萤火虫。

在样例的第二组测试数据中：一种最优的方案是选择第 1, 3, 4, 5, 7, 9, 10 只萤火虫。