Pewnego dnia mały L wybrał się na przedmieścia i odkrył nowy gatunek świetlików. Są one różnokolorowe, mają różną jasność i lubią odpoczywać w rzędzie wzdłuż drogi. Mały L upatrzył je sobie i chce złapać kilka z nich.

Wzdłuż drogi znajduje się $n$ świetlików ustawionych w rzędzie. $i$-ty świetlik ma jasność $w_i$ oraz kolor $c_i$. Mały L chce wybrać pewną liczbę świetlików (niekoniecznie sąsiadujących ze sobą) i ustawić je w rzędzie w takiej samej kolejności, w jakiej znajdowały się przy drodze. Ostateczna sekwencja świetlików musi spełniać następujące warunki:

1. Sąsiadujące świetliki muszą mieć różne kolory.
2. Jasności sąsiadujących świetlików nie mogą być względnie pierwsze (tzn. ich największy wspólny dzielnik musi być większy niż 1).

Mały L chce wiedzieć, jaka jest maksymalna liczba świetlików, które może złapać. Czy możesz mu pomóc?

Wejście

Każdy plik testowy zawiera tylko jeden zestaw danych.

Pierwsza linia zawiera liczbę całkowitą $n$ ($1 \le n \le 5 \times 10^5$), oznaczającą liczbę świetlików.

Druga linia zawiera $n$ liczb całkowitych $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 5 \times 10^5$), oznaczających jasność $i$-tego świetlika.

Trzecia linia zawiera $n$ liczb całkowitych $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 5 \times 10^5$), oznaczających kolor $i$-tego świetlika.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą maksymalną liczbę świetlików, które może złapać mały L.

Przykład

Wejście 1

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

Wyjście 1

3

Wejście 2

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

Wyjście 2

7

Uwagi

W pierwszym zestawie danych z przykładu: wszystkie świetliki mają taką samą jasność, więc każdy wybór spełnia warunek dotyczący jasności (nie są względnie pierwsze). Aby sąsiadujące świetliki miały różne kolory, jednym z optymalnych rozwiązań jest wybranie świetlików o numerach 1, 3, 5.

W drugim zestawie danych z przykładu: jednym z optymalnych rozwiązań jest wybranie świetlików o numerach 1, 3, 4, 5, 7, 9, 10.