셸든 수

셸든 쿠퍼는 가장 좋은 수가 73이라고 말한다. 본인의 표현을 그대로 옮기면 이렇다. "가장 좋은 수는 73이다. 73은 21번째 소수다. 73을 뒤집은 37은 12번째 소수이고, 12를 뒤집은 21은 7과 3을 곱한 값이다. 게다가 73을 이진법으로 쓰면 1001001이고, 거꾸로 읽어도 1001001이다. 완전히 똑같다."

소수와 회문은 이미 익숙한 소재다. 반면 73의 이진 표기에는 눈여겨볼 규칙이 하나 더 있다. 1이 1개, 0이 2개, 1이 1개, 0이 2개, 다시 1이 1개 순서로 이어진다. 이 규칙은 일반화된다. 1이 $N$개 이어진 덩어리와 0이 $M$개 이어진 덩어리를 번갈아 놓고, 1 덩어리나 0 덩어리로 끝내면 된다. 73은 $N$이 1, $M$이 2이고 덩어리가 5개다. $N$이 2, $M$이 1이고 덩어리가 4개면 110110이 되며, 이는 54의 이진 표기다.

여기서 셸든 수를 정의한다. 양의 정수의 이진 표기가 $ABABAB \dots ABA$ 꼴이거나 $ABABAB \dots AB$ 꼴이면 그 수를 셸든 수라고 한다. $A$는 모두 비트 1이 $N$개 이어진 문자열이고, $B$는 모두 비트 0이 $M$개 이어진 문자열이며, $N > 0$이고 $M > 0$이다. 표기에는 $A$가 적어도 한 번 나와야 하지만, $B$는 한 번도 나오지 않아도 된다.

셸든 수 중에는 알려진 수가 많다. 리스본 대지진이 일어난 해인 1755, 오웰의 소설 제목인 1984, 그리고 2015가 모두 셸든 수다. 셸든이 언급한 21도 셸든 수이고, 컴퓨터 딥소트가 삶과 우주와 모든 것에 관한 위대한 질문에 내놓은 답 42도 셸든 수다.

셸든 수는 무한히 많다. 두 정수가 주어질 때 그 범위에 들어가는 셸든 수의 개수를 세는 프로그램을 작성하라.

입력은 한 줄이며, 공백으로 구분된 두 정수 $X$와 $Y$가 주어진다.

$X$ 이상 $Y$ 이하인 셸든 수의 개수를 한 줄에 출력한다.

• $0 \le X \le Y < 2^{63}$