On the Land of Tiwat, there are various kind of number. But in so many numbers, we called a number "Surprising Number" if and only if it is a prime number and can be expressed as the sum of two square numbers.

A prime number is defined as a number that has no factors other than and .

A square number is defined as a number that there is an positive integer satisfying .

For example, is a prime number and , so is a "Surprising Number".

Now, give you times query, for each query you're asked to calculate how many "Surprising Number" there are in the given interval ?

The first line contains the number  denoting the times of query.

Following  lines each contains two integers  denoting the given interval.

For each query, output one line containing one integer, denoting the number of "Surprising Number" in the given interval.

2
1 5
1 10

2
2