한강 위의 집

2011년 행정안전부가 도로명에 일련번호를 붙인 새 주소 제도를 시행했다. 그로부터 수십 년이 지나, 한강 물줄기를 따라 물 위에 집을 짓는 것이 유행했다. 집은 다음과 같이 한 줄로 늘어섰다. 주소 번호만 표시한 그림이다.

북쪽 강변
---------------------------------------------------------------
(하류)  2  3  4  5  6  7  8  9  10  11  12  13  ...  N  (상류)
---------------------------------------------------------------
남쪽 강변

주소는 2번지부터 매겨진다. 강을 거슬러 올라가면서 3, 4, 5번지 순으로 번호가 이어지고 마지막 집이 $N$번지다. 1번지 집은 없다.

이 집들에는 독특한 풍습이 있다. 한 집의 주소 번호가 다른 집의 주소 번호의 배수이면 두 집은 '형제'이고, 번호가 큰 쪽이 '형', 작은 쪽이 '남동생'이다. 예를 들어 6번 집은 2번 집과 3번 집의 '형'이고, 2번 집과 3번 집은 6번 집의 '남동생'이다. 남동생 중 번호가 가장 작은 집은 '막내'가 되므로 6번 집의 막내는 2번 집이다.

'남동생'의 수가 같은 두 집은 '자매'다. 6번 집은 2번, 3번 두 집을 남동생으로 두고 8번 집은 2번, 4번 두 집을 남동생으로 두므로 두 집은 자매다. 이때 번호가 큰 8번 집이 '언니', 번호가 작은 6번 집이 '여동생'이다.

$N$번 집에는 아주 오래전에 새 주소 체계를 인터넷 지도 서비스에 적용한 노 프로그래머가 산다. 그는 자기 집의 '여동생'인 모든 집에 그동안의 자매 관계에 대한 감사의 뜻으로 선물 상자를 보내기로 했다. 그중 남동생이 한 집이라도 있고 그 '막내'의 주소 번호가 $M$ 이상인 집에는 특별한 선물을 상자에 하나 넣어 보낸다.

이 프로그래머는 특별한 선물을 모두 몇 개 준비해야 할까?

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이어지는 $T$개의 줄에 테스트 케이스가 한 줄씩 주어지며, 각 줄에는 자연수 $N$과 $M$이 공백으로 구분되어 주어진다.

N M

$N$은 특별한 선물의 개수를 계산할 집의 주소 번호이고, $M$은 막내의 주소 번호에 대한 하한이다.

제한

• $1 \le T \le 100$
• $2 \le M \le N \le 10^{12}$
• $N \le M \times 10^{6}$

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 그 케이스에서 준비해야 하는 특별한 선물의 개수다.