{"raw_statement":[{"iden":"problem statement","content":"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)$.\nSnuke is going to extract (not necessarily contiguous) subsequences from $P$ and $Q$. Here, the subsequences must satisfy the conditions below.\n\n*   The length of the subsequence extracted from $P$ and that extracted from $Q$ are the same. Below, let $k$ be this length.\n*   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$.\n\nFind the maximum possible length of each subsequence extracted by Snuke."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 200000$\n*   $P$ is a permutation of $(1,2,\\cdots,N)$.\n*   $Q$ is a permutation of $(1,2,\\cdots,N)$.\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$P_1$ $P_2$ $\\cdots$ $P_N$\n$Q_1$ $Q_2$ $\\cdots$ $Q_N$"},{"iden":"sample input 1","content":"4\n3 1 4 2\n4 2 1 3"},{"iden":"sample output 1","content":"2\n\nIf 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$."},{"iden":"sample input 2","content":"5\n1 2 3 4 5\n5 4 3 2 1"},{"iden":"sample output 2","content":"3"},{"iden":"sample input 3","content":"10\n4 3 1 10 9 2 8 6 5 7\n9 6 5 4 2 3 8 10 1 7"},{"iden":"sample output 3","content":"6"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}