Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8825

Jo'natishlar soni: 714634

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1179


So'ngi izohlar

758. Almost Prime Numbers
Vaqt limiti: 2 sekund
Xotira limiti: 64 MB

 Almost prime numbers are the non-prime numbers which are divisible by only a single prime number. In this problem your job is to write a program which finds out the number of almost prime numbers within a certain range.

    Input

First line of the input file contains an integer n (1≤n  300) which indicates how many sets of inputs are there. Each of the next n lines make a single set of input. Each set contains two integer numbers low and high (0 < low  high  1012).

   Output

  For each line of input except the first line you should produce one line of output. This line contains a single integer, which indicates how many almost prime numbers are within the range (inclusive) [low...high].

   Samples

Input

Output

1

3

1 10

1 20

1 5

3

4

1

 

Tayyorladi: Azat Yusupov
Text from: e-olimp.com
Mening urinishlarim(0) Muhokama (4) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(27) Barcha urinishlar(90)