2048번 - Hello, 2048!

문제

컴퓨터공학을 전공하고 있는 성빈은 2의 거듭제곱 수들을 다른 수들보다 특별하게 생각한다. 어느 날, 성빈은 달력을 보다가 곧 2048년이 다가온다는 사실을 알게 되었다. 성빈은 임의의 사람이 일생 중에 2의 거듭제곱 수 연도에 살아보았을 확률이 궁금해졌는데, 시간이 흐르면 흐를수록 이 확률은 낮아질 것이라는 생각이 들었다. 자신이 2048년에 직접 경험할 수 있다는 사실이 흥미로웠던 성빈은 2048이라는 숫자를 한참 바라보다가, 신기한 사실을 발견했다. 2048은 2와 4와 8이라는 또 다른 2의 거듭제곱 수들을 3개나 포함하고 있는 수였다! 그러자 성빈은 2의 거듭제곱 수들을 붙여써서 만든 수들에 대해 생각해보다가, 다음과 같은 궁금증이 생겼다.

2ドル^l, 2^{l+1}, \cdots, 2^r$을 10진법으로 표현하여 순서대로 이어 붙여 만든 새로운 10진법 수를 생각했을 때, 이 수는 몇 번이나 2로 나누어떨어질 수 있을까?

그러나 수의 크기가 너무 커지자, 계산하기가 힘들었다. 성빈을 위해 이 질문에 답을 계산하는 프로그램을 작성해 보자!

입력

첫 줄에 테스트 케이스의 개수를 의미하는 정수 $T$가 주어진다.

각 테스트 케이스마다 두 정수 $l$과 $r$이 공백으로 구분되어 입력된다.

출력

각 테스트 케이스마다 성빈의 질문에 대한 답을 한 줄에 하나씩 출력한다.

제한

• 1ドル \leq T \leq 10^5$
• 0ドル \le l \le r \le 10^9$

힌트