20615번 - Distinct Number 다국어

문제

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$.

제한

힌트

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ドル$.