题目背景

题目描述

给定长度为 $N$ 的序列 $A$ 和 $B$。

定义 $A$ 和 $B$ 两序列相乘 $A\times B$ 的规则如下，其中模数 $M=10^9+7$：

• 设 $A$ 序列为 $\{A_1,A_2,\dots,A_N\}$，$B$ 序列为 $\{B_1,B_2,\dots,B_N\}$，则相乘得到的序列为 $\{A_1B_1 \bmod M,A_2B_2 \bmod M,\dots,A_NB_N \bmod M\}$。

数学家小 G 梦想着让 $A\times B$ 得到的序列中出现次数最多的数出现的次数尽可能大。为了实现这一点，小 G 可以将 $B$ 数组任意重排列。小 G 想知道，出现次数最多的数最多出现多少次。

请你帮小 G 找到他梦想中的序列。如果小 G 获得了诺贝尔数学奖，他将会与你分享奖金。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数，表示 $A$ 序列。

第三行包含 $N$ 个整数，表示 $B$ 序列。

输出格式

一个整数，表示答案。

5
1 2 3 4 5
2 4 6 8 5

3

10
1 12 38 48 10 19 23 19 32 6
10 46 20 11 36 25 36 28 50 50

3

2
1 999999999
1 1000000000

1

提示

样例解释 #1

重排 $B$ 序列得 $\{8,4,5,2,6\}$，此时 $A\times B$ 得到的数组为 $\{8,8,15,8,30\}$，其中 $8$ 出现次数最多，出现 $3$ 次。

可以证明不存在重排 $B$ 序列的方式，使得答案大于 $3$。

数据范围

对于 $100\%$ 的数据，保证 $1 \le N \le 2000$，$1 \le A_i,B_i \le 10^9$。