서로 다른 수의 개수

시간 제한1초메모리 제한512 MB

요약

정수 x와 n개의 구간이 주어질 때, 구간 합집합에 속한 정수 i를 x와 AND 연산한 결과가 몇 종류인지 구합니다.

난이도: 어려움10점 중 8점
유형: 비트 연산, 구간, 동적 계획법
정답자: 아직 제출이 없습니다

문제

정수 $x$ 와 $n$ 개의 구간 $[l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n]$ 이 주어진다. 집합 $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]\}$ 의 크기를 구하라. 여기서 $i \operatorname{AND} x$ 는 정수 $i$ 와 $x$ 의 비트 AND이다.

입력

첫 줄에 테스트 케이스의 개수 $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$ 의 크기를 출력한다.

힌트

첫 번째 테스트 케이스에서 $S = \{0, 1\}$ 이므로 답은 $2$ 이다. 두 번째 테스트 케이스에서 $S = \{1, 2, 3\}$ 이므로 답은 $3$ 이다.

예제1

예제 1

입력

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

예상 출력

2
3
32768