考虑一种特殊情况,当从a选出来的值都一样时,可以将a提取出来使得两边相等,同理,b也是一样。
通过打表发现,只有当从a或者b中取出的元素都相同时才有可能左右相等,所以直接求a和b中最大的出现次数即可。
小红有两个长度为n的数组a1,a2,...,an和b1,b2...,bn。他想从数组a中挑选m(1≤m≤n)个整数,组成数组c;再从数组b中挑选m个整数,组成数组d,使得满足以下条件: c1≤c2≤⋅⋅⋅≤cm
b1≤b2≤⋅⋅⋅≤bm
(c1+c2+⋅⋅⋅+cm)×(d1+d2+⋅⋅⋅+dm)=m×(c1⋅d1+c2⋅d2+⋅⋅⋅+cm⋅dm)
请你帮助小红求出m的最大值。
每个测试文件均包含多组测试数据。第一行输入一个整数T(1≤T≤100),代表数据组数,每组测试数据描述如下:
第一行输入一个整数n(1≤n≤105)代表数组中的元素数量。
第二行输入n个数a1,a2,...,an(1≤ai≤2×109)代表数组中的元素。
第三行输入n个数b1,b2,...,bn(1≤bi≤2×109)代表数组中的元素。
除此之外,保证所有的n之和不超过105。
对于每一组测试数据,在一行上输出一个整数,表示m的最大值。
输入
2
3
1 2 3
2 2 3
1
6
8
输出
2
1
说明
对于第一组样例:c={1,3},d={2,2}。
对于第二组样例:c={1}、d={2}。