题目描述
We say that a odd number N is similar to 2017 when both N and (N+1)/2 are prime.
You are given Q queries.
In the i-th query, given two odd numbers l_i and r_i, find the number of odd numbers x similar to 2017 such that l_i ≤ x ≤ r_i.
Constraints
- 1≤Q≤10^5
- 1≤l_i≤r_i≤10^5
- l_i and r_i are odd.
- All input values are integers.
Input
Input is given from Standard Input in the following format:
Q
l_1 r_1
:
l_Q r_Q
Output
Print Q lines. The i-th line (1≤i≤Q) should contain the response to the i-th query.
Examples
Input
1
3 7
Output
2
Input
4
13 13
7 11
7 11
2017 2017
Output
1
0
0
1
Input
6
1 53
13 91
37 55
19 51
73 91
13 49
Output
4
4
1
1
1
2
输入格式
见题面
输出格式
见题面
样例输入
1
3 7
样例输出
2