비밀번호 486

문제 정보

문제

재훈이는 한 번 담배를 끊겠다고 다짐할 때마다 이메일 계정 비밀번호를 바꾸는 습관이 있습니다. 재훈이는 비밀번호를 항상 "no-smok**X**" 와 같이 정하는데, 여기서 X는 1자리 이상의 자연수입니다. 재훈이에게는 k번째로 금연을 다짐할 때는 항상 정확히 k개의 약수를 갖는 숫자로 X를 선택하는 습관이 있습니다. 예를 들어 재훈이가 12번째로 금연을 다짐했을 때 쓴 비밀번호는 no-smok486 이었습니다. 486 에는 1, 2, 3, 6, 9, .., 243, 486으로 모두 12개의 약수가 있으니까요.

재훈이는 금연을 다짐하고 비밀번호를 바꾼 뒤 잠들었는데, 아침에 일어나서는 비밀번호가 기억나지 않는다는 사실을 깨달았습니다. 재훈이가 어렴풋이 기억하는 것은 비밀번호가 n개의 약수를 가진다는 사실과, 비밀번호가 아마도 [lo,hi] 범위 내에 있을 거라는 것 뿐입니다 (범위는 양 끝의 수를 포함합니다).

재훈이가 예상한 범위 내에 비밀번호가 될 수 있는 수가 몇 개나 되는지 계산하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 c(c <= 50)가 주어집니다. 그 후 c줄에 각 3개의 정수로 n (n < 400), lo , hi(1 <= lo <= hi <= 10,000,000)이 주어집니다. hi-lo 는 항상 1백만 이하입니다.

출력

각 테스트 케이스마다, 해당 범위 내에 비밀번호가 될 수 있는 숫자가 몇 개인지 출력합니다.

예제 입력

3
2 2 10
12 486 486
200 1000000 2000000 

예제 출력

4
1
19

노트

5개의 댓글이 있습니다.