Monocarp 计划举办武术锦标赛。根据重量将分为三个级别:轻量级、中量级和重量级。每个组别的获胜者将通过单场淘汰制决出。
特别是,这意味着每个部门的参与者数量应该是 2 的幂。此外,每个部门的参与者数量应不为零。
目前已有 $$$n$$$ 名参赛者报名参加比赛,其中第 $$$i$$$ 的体重为 $$$a_i$$$。为了将参与者分成不同的组,Monocarp 将建立两个整数权重边界 $$$x$$$ 和 $$$y$$$ ($$$x < y$$$)。
所有体重严格低于 $$$x$$$ 的参与者将被视为轻量级。所有体重大于或等于 $$$y$$$ 的参与者将被视为重量级。其余的参赛者将被视为中量级。
分布可能不会使每个组的参与者数量达到 2 的幂。它还可能导致空分裂。为了解决这些问题,Monocarp 可以邀请任意数量的参与者加入每个部门。
请注意,Monocarp 无法踢出任何已注册锦标赛的 $$$n$$$ 参与者。
然而,他希望邀请尽可能少的额外参与者。帮助 Monocarp 选择 $$$x$$$ 和 $$$y$$$,使得所需的额外参与者总数尽可能小。输出该数量。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 注册参与者的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$) - 注册参与者的权重。
所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - Monocarp 在选择权重边界 $$$x$$$ 和 $$$y$$$ 后需要邀请的最小额外参与者数量。
示例
输入 #1
4 4 3 1 2 1 1 1 6 2 2 2 1 1 1 8 6 3 6 3 6 3 6 6
输出 #1
0 2 3 2
注意
在示例的第一个测试用例中,Monocarp 可以选择 $$$x=2$$$ 和 $$$y=3$$$。轻量级、中量级和重量级的参赛者分别为 $$$2$$$、$$$1$$$ 和 $$$1$$$。它们都是二的幂,因此不需要额外的参与者。
在示例的第二个测试用例中,无论选择 $$$x$$$ 和 $$$y$$$,一个部门将有 $$$1$$$ 参与者,其余将有 $$$0$$$ 参与者。因此,Monocarp 将不得不邀请 $$$1$$$ 参与者加入剩余的两个部门。
在示例的第三个测试用例中,Monocarp 可以选择 $$$x=1$$$ 和 $$$y=2$$$。轻量级、中量级和重量级的参赛者分别为 $$$0$$$、$$$3$$$ 和 $$$3$$$。因此,每个部门都需要一名额外的参与者。
在示例的第四个测试用例中,Monocarp 可以选择 $$$x=8$$$ 和 $$$y=9$$$。轻量级、中量级和重量级的参赛者分别为 $$$8$$$、$$$0$$$ 和 $$$0$$$。中量级和重量级各需要一名额外的参赛者。