Problem Statement

Given are permutations $P=(P_1,P_2,\cdots,P_N)$ and $Q=(Q_1,Q_2,\cdots,Q_N)$ of $(1,2,\cdots,N)$.
Snuke is going to extract (not necessarily contiguous) subsequences from P and Q.
Here, the subsequences must satisfy the conditions below.

• The length of the subsequence extracted from P and that extracted from Q are the same. Below, let k be this length.
• Let $a=(a_1,a_2,\cdots,a_k)$ and $b=(b_1,b_2,\cdots,b_k)$ be the subsequences extracted from P and Q, respectively.
  Then, for each $1 \leq i \leq k, b_i$ is a multiple of a_i.

Find the maximum possible length of each subsequence extracted by Snuke.

Input

Input is given from Standard Input in the following format:
N
$P_1 P_2 \cdots P_N$
$Q_1 Q_2 \cdots Q_N$

Output

Print the answer.

Constraints

• $1 \leq N \leq 200000$
• P is a permutation of $(1,2,\cdots,N)$.
• Q is a permutation of $(1,2,\cdots,N)$.
• All values in input are integers.

Sample Input 1

4
3 1 4 2
4 2 1 3

Sample Output 1

2

If we extract the subsequence (1,2) from P and (4,2) from Q, they satisfy the conditions.
It is impossible to extract subsequences of length 3 or greater to satisfy the conditions, so the answer is 2.

Sample Input 2

5
1 2 3 4 5
5 4 3 2 1

Sample Output 2

3

Sample Input 3

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

Sample Output 3

6

见题面 Input 部分

见题面 Output 部分