#1045 소수 구하기 II

349  1 s   128 MB  

Description

소수란 $1$과 자기 자신을 제외한 그 어떤 수로도 나누어 떨어지지 않는 수를 말한다.

예를 들어 $2, 3, 5, 7$ 은 $1$과 자기 자신을 제외한 어떤 수로도 나누어 떨어지지 않으므로 소수지만 $4$는 $1$과 자기 자신 이외에도 $2$로 나누어 떨어지기 때문에 소수가 아니다.

두 수를 $a$, $b$를 입력받았을 때 $a$이상 $b$이하의 수 중에서 소수가 몇 개인지 찾는 프로그램을 작성하라.

Input

맨 처음 테스트 케이스의 개수 $T$ $(1 \leq T \leq 20)$를 입력받는다.

그 뒤에 $T$의 개수만큼 $a$, $b$를 입력받는다. $(2 \leq a < b \leq 10,000)$

Output

각 테스트 케이스마다 $a$, $b$ 사이에 존재하는 소수의 개수를 출력한다.

Sample Input

Sample Output

3
2 10
50 100
100 1000
4
10
143