解题思路

设整个数组的按位与结果为 $A$。

删除某个元素 $a_i$ 后，剩余元素的按位与结果只可能在某些二进制位上从 $0$ 变成 $1$，不会让 $A$ 中原本为 $1$ 的位变成 $0$。

因此，删除 $a_i$ 后结果严格变大，当且仅当存在某个二进制位满足：

• 该位在 $A$ 中为 $0$

题目内容

给定一个长度为 $n$ 的正整数数组 {$a_1, a_2, ..., a_n$}，记整个数组中所有数按位与的结果为 $A$。

你想统计有多少个下标 $i$，满足删除 $a_i$ 之后，剩下所有数的按位与的结果严格变大。

输入描述

每个测试文件包含多组测试数据。第一行输入一个整数 $T(1 \le T \le 2 \times 10^5)$，表示测试组数。每组测试数据描述如下：

第一行输入一个整数 $n(2 \le n \le 2 \times 10^5)$，表示数组长度。

第二行输入 $n$ 个整数 $a_1, a_2, ..., a_n(1 \le a_i \le 10^9)$，表示数组元素。

保证单个测试文件的 $n$ 之和不超过 $3 \times 10^5$。

输出描述

对于每一组测试数据，新起一行输出一个整数，表示满足条件的下标数量。

样例1

输入

3
5
7 3 7 7 7
3
1 1 1
2
2 1

输出

1
0
2

说明

第二组：无论删除哪个 $1$，其余元素的按位与仍为 $1$，不会变大，所以答案为 $0$。

第三组：原数组整体按位与为$2$ & $1 = 0$。删除任一元素后，剩下一个数本身即为按位与：分别为 $2$ 或 $1$，都大于 $0$，因此答案为 $2$。