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

Notes

In the first sample case, all fireflies have the same brightness, so any selection satisfies the "not coprime" requirement. To ensure adjacent fireflies have different colors, one optimal strategy is to choose the 1st, 3rd, and 5th fireflies.

In the second sample case, one optimal strategy is to choose the 1st, 3rd, 4th, 5th, 7th, 9th, and 10th fireflies.