Однажды маленький Л. отправился за город и обнаружил необычных светлячков. Они были самых разных цветов и яркости, и любили выстраиваться в ряд вдоль дороги. Маленький Л. присмотрел их и захотел поймать некоторых из них.

Всего вдоль дороги в ряд выстроилось $n$ светлячков. У $i$-го светлячка яркость равна $w_i$, а цвет — $c_i$. Маленький Л. хочет выбрать из них некоторое подмножество (не обязательно идущих подряд) и выстроить их в ряд в том же порядке, в котором они стояли вдоль дороги. Итоговая последовательность светлячков должна удовлетворять следующим условиям:

1. Цвета соседних светлячков должны быть различными.
2. Яркости соседних светлячков не должны быть взаимно простыми.

Теперь маленький Л. хочет узнать, какое максимальное количество светлячков он может поймать. Вы можете ему помочь?

Входные данные

Каждый файл теста содержит только один набор входных данных.

Первая строка содержит целое число $n$ ($1 \le n \le 5 \times 10^5$), количество светлячков.

Вторая строка содержит $n$ целых положительных чисел $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 5 \times 10^5$), яркости светлячков.

Третья строка содержит $n$ целых положительных чисел $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 5 \times 10^5$), цвета светлячков.

Выходные данные

Выведите одно целое число — максимальное количество светлячков, которое может поймать маленький Л.

Примеры

Входные данные 1

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

Выходные данные 1

3

Входные данные 2

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

Выходные данные 2

7

Примечание

В первом примере: яркость всех светлячков одинакова, поэтому любое подмножество удовлетворяет условию «не взаимно просты». Чтобы цвета соседних светлячков были различными, одним из оптимальных вариантов является выбор светлячков с индексами 1, 3, 5.

Во втором примере: одним из оптимальных вариантов является выбор светлячков с индексами 1, 3, 4, 5, 7, 9, 10.