Bilangan Hampir-Prima

Bilangan hampir-prima adalah bilangan bukan prima yang hanya habis dibagi oleh satu, dirinya sendiri dan bilangan-bilangan prima lain yang lebih kecil.

Contoh:

• 21 adalah bilangan hampir-prima karena 21 hanya habis dibagi 1, 3, 7 dan 21 (3 dan 7 adalah bilangan prima).
• 13 bukan bilangan hampir-prima karena 13 sendiri adalah bilangan prima.
• 24 bukan bilangan hampir-prima karena 24 habis dibagi 4, 6, 8, 12 yang bukan merupakan biangan prima.

Diberikan dua buah bilangan bulat A dan B, tentukan ada berapa bilangan hampir-prima yang berada pada rentang A dan B, inklusif.

Input

Baris pertama berisi sebuah bilangan bulat T (T ≤ 100) yang menyatakan jumlah kasus. Setiap kasus terdiri dari dua buah bilangan bulat A dan B (2 ≤ A ≤ B ≤ 1.000).

Output

Untuk setiap kasus, output dalam satu baris sebuah bilangan bulat yang menyatakan banyaknya bilangan hampir-prima yang berada pada rentang A dan B, inklusif.

3
2 20
10 30
5 100

6
7
33

Penjelasan untuk contoh input 1.

Bilangan hampir-prima yang berada pada rentang 2...20: 4, 6, 9, 10, 14 dan 15.