1003. 张力

题目描述

胖胖龙正在研究一种数字排列艺术。他认为，对于任意两个非负整数 x, y，将它们相邻放置时会产生大小为 lowbit(x ⊕ y) 的“张力”。现在，胖胖龙有一个长度为 n 的非负整数序列 a1, a2, …, an。他希望

将这些数重新排列成 b1, b2, …, bn，使得相邻数字之间的总张力最

小，即最小化：n−1

∑ lowbit(bi ⊕ bi+1 )

i=1

其中 ⊕ 表示按位异或。对于正整数 x，lowbit(x) 表示 x 二进制表示下最低位的 1 对应的数值，例如 lowbit(12) = 4。特别地，我们定义 lowbit(0) = 0。请你帮帮胖胖龙，求出最小可能的总张力。

输入格式

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 T (

1 ≤ T ≤ 100)，表示数据组数。对于每组测试数据：第一行一个正整数 n (1 ≤ n ≤ 5 × 103 )，表示序列的长度。第二行 n 个整数 a1, a2, …, an (0 ≤ ai < 250 )，表示序列 a。

保证所有测试数据中 n 之和不超过 2 × 104。

输出格式

对于每组测试数据：输出一行一个整数，表示最小可能的总张力。

样例输入

3
3
0 1 2
5
3 4 5 6 7
8
1 8 2 0 12 1 4 2

样例输出

2
4
8

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第2场）