배수
시간 제한5초메모리 제한1024 MB
a와 b가 주어졌을 때, 1부터 b까지의 정수 중 2 이상 a 이하의 정수 가운데 하나로 나누어떨어지는 수의 개수를 구합니다.
문제
Sumon의 아홉 살 아들 Samin은 프로그래밍을 좋아한다. 그는 프로그램이 컴파일되고, 실행되고, 올바른 출력을 낼 때(적어도 작은 테스트 케이스에서) 기뻐한다. 실행 시간을 효율적으로 만드는 데에는 별로 신경 쓰지 않는다. 2016 UCF Local Programming Contest 전까지 Samin의 생활은 편안했다.
남동생 Saraf는 2016 UCF Practice Local Contest가 끝난 바로 다음 날 태어났고, 진짜 Local Contest에 꼭 나가고 싶어 한다. 여러 사정으로 Saraf는 태어난 지 "6" (2+2+2) 일, 즉 특별한 "2 0 16" (= 2 0 22*2 = 2 0 (2*2)2 ) UCF Local Contest에 나가지 못했다. Saraf는 프로그래밍에 대한 날카로운 감각을 기를 운명이며, 형의 프로그래밍 생활을 더 힘들게 만들 것이다. Saraf는 Samin이 중간 크기와 큰 테스트 케이스를 최소 20번 이상 실행해서 코드 효율을 확인하기를 원한다. Samin의 코드가 충분히 빨리 돌아가지 않으면 Saraf는 화를 내며 노트북 앞에 앉아 결과가 나올 때까지 계속 두드린다.
Samin은 학교 프로젝트를 마쳐야 한다. Saraf의 분노로부터 노트북을 지키기 위해, 이 문제에 대해 시간 효율이 가장 좋은 풀이를 작성해 달라.
두 정수 a와 b가 주어진다. 1 ≤ b_i ≤ b인 정수 b_i 중에서, 2 ≤ a_i ≤ a인 정수 a_i 중 하나 이상의 배수인 것이 몇 개인지 구하라. 예를 들어 a = 3, b = 30이면 1부터 30까지의 정수 중 2 또는 3의 배수는 20개이다.
입력
첫 줄에 질의의 개수를 나타내는 양의 정수 n (1 ≤ n ≤ 100)이 주어진다. 각 질의는 한 줄에 공백으로 구분된 두 정수 a, b로 주어지며, , 이다.
출력
각 질의마다 1부터 b까지의 정수 중 2부터 a까지의 정수 중 하나 이상의 배수인 것의 개수를 한 줄에 하나씩 출력한다.