시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB21150.000%

문제

Given $n$ intervals $[l_1,r_1], [l_2,r_2], \ldots, [l_n, r_n]$ and an integer $x$, you should find the size of the set $S = \{y \mid y = i \operatorname{AND} x, \, i \in [l_1, r_1] \cup [l_2, r_2] \cup \ldots \cup [l_n, r_n]\}$, where $i\operatorname{AND} x$ is the bitwise and of integers $i$ and $x$.

입력

There are multiple test cases. The first line of input contains an integer $T$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $x$ ($1 \le n \le 5 \cdot 10^3$, $0 \le x \le 10^{18}$).

Each of the next $n$ lines contains two integers $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 10^{18}$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5 \cdot 10^3$.

출력

For each test case, output an integer denoting the size of the set $S$.

예제 입력 1

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

예제 출력 1

2
3
32768

힌트

For the first sample test case, we have $S = \{0, 1\}$, so the answer is $2$.

For the second sample test case, we have $S = \{1, 2, 3\}$, so the answer is $3$.