题目描述

t次查询 输出n到m之间的素数个数。

输入格式

第一行一个整数t

1≤t≤1e5


以下t行每行两个整数 n m 


1≤n≤m≤1e8

输出格式

t行，每行一个整数，n到m之间的素数个数

5
1 100000000
114 514
123 456
13360 65617
10010 10086

5761455
67
57
4969
6