China is one of the strongest countries in the world in the sense of economy and military technology. Tom is from the United States. Professionally he is a tourist. He has recently come to china. Unfortunately, a virus called the "Corona" outbreak in china. So, he is in trouble. If he wants to leave china then he must go to Beijing. The main problem is that he has to cross some provinces to reach Beijing. Some of them are affected by "Coronavirus-19" and it's too dangerous. But he is very smart as well. He calculated that the provinces which are primes are safe for him. As you are a talented programmer so he asks you to do this task.
Note: A quarantine is a restriction on the movement of people and goods which is intended to prevent the spread of disease or pests.
Input
Input starts with an integer N which denotes the number of test cases.
Each case contains a line containing two integers X and Y which denotes the provinces.
Constraints
1 ≤ X ≤ Y ≤ 1000000000
≝(X,Y)≤100000
1 ≤ N ≤ 200
Output
For each case print the number of provinces which are safe.
Sample
| Input | Output |
|---|---|
3 2 3 5 11 1 100 | 2 3 25 |
