Polycarp 被赋予了一个长度为 $$$n$$$ 的数组 $$$a$$$。 Polycarp 认为如果存在一个数字 $$$C$$$,则数组是美丽的,这样数组中的每个数字要么出现零次,要么出现 $$$C$$$ 次。 Polycarp 想要从数组 $$$a$$$ 中删除一些元素以使其美观。
例如,如果 $$$n=6$$$ 且 $$$a = [1, 3, 2, 1, 4, 2]$$$,则以下选项可以使数组 $$$a$$$ 数组变得漂亮:
- Polycarp 删除位置 $$$2$$$ 和 $$$5$$$ 处的元素,数组 $$$a$$$ 变得等于 $$$[1, 2, 1, 2]$$$;
- Polycarp 删除位置 $$$1$$$ 和 $$$6$$$ 处的元素,数组 $$$a$$$ 变得等于 $$$[3, 2, 1, 4]$$$;
- Polycarp 删除位置 $$$1、2$$$ 和 $$$6$$$ 处的元素,数组 $$$a$$$ 变得等于 $$$[2, 1, 4]$$$;
帮助 Polycarp 确定从数组 $$$a$$$ 中删除的最小元素数,以使其美观。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
每个测试用例的第一行由一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) 组成 - 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数——Polycarp 必须从数组 $$$a$$$ 中删除的最小元素数量,以使其美观。
示例
输入 #1
3 6 1 3 2 1 4 2 4 100 100 4 100 8 1 2 3 3 3 2 6 6
输出 #1
2 1 2