시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 2 | 1 | 1 | 50.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$.
3 2 1 1 2 343 34345 1 3 1 3 1 123242343 1 1000000000000000000
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$.