题解

题目描述

小苯有一个长度为 n 的数组 a，他可以通过以下操作来改变数组：

• 对于每个 i，将 b[i] 设为 a[i] | a[(i+1)%n]，然后将 a 替换为 b。

要求找到最少需要多少次操作，使得数组 a 的最小值不小于 k。题目保证有解。

思路分析

题目内容

小苯有一个长为 $n$ 的数组 $a$，下标从 $0$ 到 $n-1$ ，他可以做如下操作:

• 对于每一个 $i(1 ≤ i ≤ n)$，令 ${b_i}={a_i}|a_{(i+1)％n}$，全部执行完后，再将 $a$ 数组赋值为 $b$数组，即再执行：$a_i =b_i(1≤i≤n)$。

小苯想知道，如果他想要 $a$ 的最小值不小于 $k$ 的话，最少需要执行多少次上述的操作，请你帮他算一算吧。(数据保证有解)。

输入描述

每个测试文件内都包含多组测试数据。

第一行一个正整数 $T(1 ≤ T≤ 1000)$，表示测试数据的组数

接下来对于每组测试数据，输入包含两行。

第一行两个整数 $n,k(1≤n≤2*10^5,0≤k≤2^{31})$表示数组 $a$ 的长度和最小值的限制。

第二行 $n$ 个整数 $a_i(0 ≤ a_i< 2^{31})$，表示数组 $a$。(保证所有测试数据中 $n$ 的总和不超过 $3*10^5$。

输出描述

输出包含 $T$ 行，对于每组测试数据，输出一行一个整数，表示最少要执行几次操作。

样例1

输入

1
5 4
1 7 4 2 7

输出

1

说明

只需操作 $1$ 次，数组 $a$ 变为：

{$7,7,6,7,7$}，满足最小值不小于 $4$ 。