Gọi ~Q~ là số được viết theo thứ tự ngược lại của số tự nhiên ~P~. Khi đó ~P~ gọi là số nguyên tố Song sinh nếu thỏa mãn đồng thời các điều kiện sau:

• ~P \ne Q~;

• ~P~ và ~Q~ đều là các số nguyên tố.

Chẳng hạn: Số ~13~ là số nguyên tố Song sinh vì khi viết ngược lại ta được số ~31~ (~31 \ne 13~; đồng thời ~13~ và ~31~ đều là số nguyên tố). Các số ~7, 11, 14, 23~ không là số nguyên tố Song sinh.

Yêu cầu: Với mỗi cặp số tự nhiên ~a, b~ hãy đếm số lượng số nguyên tố Song sinh thuộc đoạn ~[a, b]~.

Input

• Dòng đầu tiên ghi số nguyên dương ~T~ là số lượng cặp số tự nhiên ~(T \le 10^6)~.

• ~T~ dòng tiếp theo, mỗi dòng chứa hai số tự nhiên ~a, b~ ~(1 \le a \le b \le 10^6)~.

Output

Gồm ~T~ dòng, mỗi dòng chứa một số nguyên là số lượng số nguyên tố Song sinh tương ứng với mỗi cặp số tự nhiên ở trên.

Scoring

Sample Input 1

3
3 15
2 10
1 31

Sample Output 1

1
0
3

Notes

Đoạn ~[3, 15]~ có ~1~ số nguyên tố Song sinh là số ~13~.

Đoạn ~[2, 10]~ không có số nguyên tố Song sinh.

Đoạn ~[1, 31]~ có ~3~ số nguyên tố Song sinh: ~13, 17~ và ~31~.