7kfMof - Online IDE & Debugging Tool

#[allow(unused_imports)]
use std::io::{BufWriter, stdin, stdout, Write};

#[derive(Default)]
struct Scanner { buf: Vec<String> }
impl Scanner {
    fn next<T: std::str::FromStr>(&mut self) -> T {
        loop {
            if let Some(tok) = self.buf.pop() {
                return tok.parse().ok().unwrap();
            }
            let mut s = String::new();
            stdin().read_line(&mut s).unwrap();
            self.buf = s.split_whitespace().rev().map(String::from).collect();
        }
    }
}

#[allow(unused_variables)]
macro_rules! io_init { ($scan:ident,$out:ident) => {
    let mut $scan = Scanner::default();
    let $out = &mut BufWriter::new(stdout());
}}

macro_rules! read { ($scan:ident, $($v:pat=>$t:ty),*) => { $(let $v = $scan.next::<$t>();)* }; }

fn solve(primes: &Vec<usize>, scan: &mut Scanner, out: &mut BufWriter<std::io::Stdout>) {
    read!(scan, l0=>i64, r0=>i64);
    let l = l0 * 2;
    let r = r0 * 2;
    let m = (r - l + 1) as usize;
    let mut vis = vec![true; m];
    for &p in primes {
        let p = p as i64;
        if p * p > r { break; }
        let start = ((l + p - 1) / p).max(2) * p;
        let mut j = start;
        while j <= r {
            vis[(j - l) as usize] = false;
            j += p;
        }
    }
    let mut pre = vec![-1isize; m];
    for i in 1..m {
        pre[i] = if vis[i] { i as isize } else { pre[i-1] };
    }
    let mut nex = vec![-1isize; m];
    for i in (0..m-1).rev() {
        nex[i] = if vis[i] { i as isize } else { nex[i+1] };
    }
    let mut mi = m as isize;
    let mut cnt = 0i64;
    fn dfs(l: isize, r: isize, pre: &Vec<isize>, nex: &Vec<isize>, mi: &mut isize, cnt: &mut i64) {
        if r - l < *mi {
            *mi = r - l;
            *cnt = 1;
        } else if r - l == *mi {
            *cnt += 1;
        }
        let mid1 = (l + r) / 2;
        let x = pre[mid1 as usize];
        if x != -1 && x > l {
            dfs(x, r, pre, nex, mi, cnt);
        }
        let mid2 = (l + r + 1) / 2;
        let y = nex[mid2 as usize];
        if y != -1 && y < r {
            dfs(l, y, pre, nex, mi, cnt);
        }
    }
    dfs(0, (m-1) as isize, &pre, &nex, &mut mi, &mut cnt);
    writeln!(out, "{}", cnt).unwrap();
}

fn main() {
    io_init!(scan,out);
    let maxn = 2_000_000;
    let mut is_comp = vec![false; maxn+1];
    let mut primes = Vec::new();
    for i in 2..=maxn {
        if !is_comp[i] {
            primes.push(i);
        }
        for &p in &primes {
            let x = i * p;
            if x > maxn { break; }
            is_comp[x] = true;
            if i % p == 0 { break; }
        }
    }
    read!(scan, T=>usize);
    for _ in 0..T {
        solve(&primes, &mut scan, out);
    }
}