题目描述

【题目大意】

给定两个长度为 $n(n\le 2\times 10^5)$ 的 $1\sim n$ 的排列 $\text{P}$ 和 $\text{Q}$。

现在需要在 $\text{P}$ 和 $\text{Q}$ 中分别取出长度为 $k$ 两个子序列 $\text{A}$ 和 $\text{B}$，满足 $\forall i\in [1,k],a_i\mid b_i$。

最大化 $k$，求 $k$。

输入格式

共三行。

第一行一个整数 $n$。

第二行 $n$ 个整数表示排列 $\text{P}$。

第三行 $n$ 个整数表示排列 $\text{Q}$。

输出格式

一行一个整数 $k$ 表示答案。

样例 1

输入

4
3 1 4 2
4 2 1 3

输出

2

样例 2

输入

5
1 2 3 4 5
5 4 3 2 1

输出

3

样例 3

输入

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

输出

6