12435번 - 한강 (Small)

문제

2011년 행정안전부에서는 도로명에 일련번호를 붙인 도로명 주소(새 주소) 제도를 시행하였다. 그로부터 수십년이 지났고, 한강의 물줄기를 따라서 물 위에 집을 짓는 것이 유행하였다. 이 새로운 유행에서는 다음과 같이 일렬로 집들이 만들어졌다. (주소 번호만 표시)

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

주소는 2번지부터 매겨지고, 한강변을 거슬러 올라가면서 다음 집들에 3, 4, 5... 번지로 주소가 매겨진다.

이 집들에 사는 사람들끼리 공유하는 특이한 풍습이 하나 있었는데, 한 집의 주소 번호가 다른 집의 주소 번호의 배수가 되는 경우, 두 집은 서로 '형제 관계' 라고 불렀고, 번호가 큰 쪽이 '형', 작은 쪽이 '남동생' 이 되었다. 예를 들어서 6번 집은 2, 3번 집에게 '형'이 되고, 2, 3번 집은 6번 집에게 '남동생' 이 된다. 또한 남동생 중 번호가 가장 작은 집이 ‘막내' 가 되어, 이 경우 2번 집은 6번 집의 ‘막내' 가 된다.

'남동생'의 수가 같은 집들끼리는 또한 친목 관계가 있었는데, 이것을 '자매 관계' 라 불렀다. 예를 들어서 6번 집은 2, 3번 집의 두 '남동생' 이 있고, 8번 집은 2, 4번 집의 두 '남동생' 이 있으므로, 두 집은 '자매' 관계가 된다. 이때 번호가 큰 8번 집을 '언니', 번호가 작은 6번 집을 '여동생' 이라고 불렀다.

N번 집에는 오랜 과거에 새주소 시스템을 인터넷 지도 서비스에 적용시킨 노 프로그래머가 살고 있었다. 그는 자신의 집의 '여동생' 인 집들에게 그 동안의 '자매' 관계에 대한 감사의 뜻으로 선물 상자를 보내기로 했다. 특히 그 선물 상자를 받는 집이 '남동생' 관계의 집들을 가지고 있고 그 중 '막내'의 집 번호가 M 이상일 경우에는, 어떤 특별한 선물을 선물 상자에 하나 넣어서 보내기로 하였다.

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

입력

입력의 첫 줄에는 테스트 케이스의 숫자 T가 주어진다. 아래로 T 줄의 입력이 주어지며 각 줄은 하나의 테스트 케이스에 대한 입력이다. 각 테스트 케이스는 아래와 같이 2개의 자연수로 주어진다.

N M

여기서 N은 장난감의 수를 계산해야 할 집의 주소 번호이고, M은 막내 주소의 최소 제한이다.

제한

• 1 ≤ T ≤ 1000.
• 2 ≤ M ≤ N.
• 2 ≤ N ≤ 10^6.

출력

각 테스트 케이스에 대한 출력은 "Case #x: y" 형태로 이루어져야 한다. x는 1부터 시작되는 케이스 번호이고, y는 각 케이스에 대해서 준비해야 하는 특별한 선물의 개수이다.

제한

힌트