给定 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$ 和一个整数 $x$，你需要求出集合 $S = \{y \mid y = i \text{ AND } x, i \in [l_1, r_1] \cup [l_2, r_2] \cup \dots \cup [l_n, r_n]\}$ 的大小，其中 $i \text{ AND } x$ 表示整数 $i$ 与 $x$ 的按位与运算。

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $x$ ($1 \le n \le 5 \cdot 10^3$, $0 \le x \le 10^{18}$)。

接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$ ($0 \le l_i \le r_i \le 10^{18}$)。

保证所有测试数据中 $n$ 的总和不超过 $5 \cdot 10^3$。

对于每组测试数据，输出一个整数，表示集合 $S$ 的大小。

样例

输入格式 1

3
2 1
1 2
343 34345
1 3
1 3
1 123242343
1 1000000000000000000

输出格式 1

2
3
32768

说明

对于第一个样例，我们有 $S = \{0, 1\}$，因此答案为 $2$。

对于第二个样例，我们有 $S = \{1, 2, 3\}$，因此答案为 $3$。