ある日、小Lは郊外で、色とりどりで明るさも様々な、道端に一列に並んで生息する珍しいホタルを見つけました。小Lはそれらに目をつけ、何匹か捕まえたいと考えました。

道端には $n$ 匹のホタルが一列に並んでおり、$i$ 番目のホタルの明るさは $w_i$、色は $c_i$ です。小Lはそこから何匹か（連続していなくてもよい）を捕まえ、道端にいた時の順序で一列に並べようとしています。最終的なホタルの列は、以下の条件を満たす必要があります。

1. 隣り合うホタルの色は異なる。
2. 隣り合うホタルの明るさは互いに素ではない（最大公約数が 1 より大きい）。

小Lは、最大で何匹のホタルを捕まえられるかを知りたがっています。彼を助けてあげてください。

入力

各テストファイルにはテストデータが1つだけ含まれます。

第一行には整数 $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$) が含まれ、$i$ 番目のホタルの明るさを表します。 第三行には $n$ 個の正整数 $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 5 \times 10^5$) が含まれ、$i$ 番目のホタルの色を表します。

出力

小Lが捕まえられるホタルの最大数を一行で出力してください。

入出力例

入力 1

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

出力 1

3

注記

サンプル1のテストデータにおいて、すべてのホタルの明るさは同じであり、どのような選び方でも「互いに素ではない」という条件を満たします。隣り合うホタルの色が異なるようにする最適な方法の一つは、1番目、3番目、5番目のホタルを選ぶことです。

入力 2

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

出力 2

7

注記

サンプル2のテストデータにおいて、最適な方法の一つは、1番目、3番目、4番目、5番目、7番目、9番目、10番目のホタルを選ぶことです。