github.com/captn3m0/codechef.git

---
category_name: easy
problem_code: PRETNUM
problem_name: 'Yet Another Cute Girl'
languages_supported:
    - ADA
    - ASM
    - BASH
    - BF
    - C
    - 'C99 strict'
    - CAML
    - CLOJ
    - CLPS
    - 'CPP 4.3.2'
    - 'CPP 4.9.2'
    - CPP14
    - CS2
    - D
    - ERL
    - FORT
    - FS
    - GO
    - HASK
    - ICK
    - ICON
    - JAVA
    - JS
    - 'LISP clisp'
    - 'LISP sbcl'
    - LUA
    - NEM
    - NICE
    - NODEJS
    - 'PAS fpc'
    - 'PAS gpc'
    - PERL
    - PERL6
    - PHP
    - PIKE
    - PRLG
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '1 - 2'
source_sizelimit: '50000'
problem_author: ballon_ziq
problem_tester: null
date_added: 15-08-2013
tags:
    - ballon_ziq
    - easy
    - nov13
    - prime
    - sieve
editorial_url: 'http://discuss.codechef.com/problems/PRETNUM'
time:
    view_start_date: 1384162200
    submit_start_date: 1384162200
    visible_start_date: 1384162200
    end_date: 1735669800
    current: 1493558176
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/NOV13/mandarin/PRETNUM.pdf) and [Russian](http://www.codechef.com/download/translated/NOV13/russian/PRETNUM.PDF).

Chef doesn't love math anymore. He loves Sasha. Sashen'ka is cute.

Chef goes on a date with her. Flowers are boring, while numbers are not. He knows that most of all this girl loves numbers, that's why he is going to bring ribbon with numbers **L, L+1, L+2, ..., R** written on it.

Sasha thinks that numbers with prime number of divisors are special. That's why she is going to kiss boy for each such number he will bring.

Now Chef wonder how many times he will be kissed by Sashen'ka ?

### Input

The first line of the input contains an integer **T** denoting the number of test cases. The description of **T** test cases follows.
The first line of each test case contains two number **L, R**.

### Output

For each test case, output a single line containing answer for corresponding test case.

### Constraints

- **1** ≤ **T** ≤ **5**
- **1** ≤ **L** ≤ **R** ≤ **1012**
- 0 ≤ **R-L** ≤ **106**

### Example

<pre><b>Input:</b>
1
1 10

<b>Output:</b>
6
</pre>### Explanation

**Example case 1.** Numbers 2,3,4,5,7,9 are special.