该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

一天阿贝多和砂糖聊起了素数。砂糖说：“素数又名质数，素数的定义是指在大于 $1$ 的自然数中，除了 $1$ 和它本身以外不再有其他因数的自然数。”

a 是一个自然数，如果

$a =6×k$,( $k ≥1$ 且为整数),$a$ 因为有因数 $6$ ，不会是素数。

$a =6×k+2$,$a$ 一定有因数 $2$ ,不会是素数。

$a =6×k+3$,$a$ 一定有因数 $3$ ,不会是素数。

$a =6×k+4$,$a$ 一定有因数 $2$ ,不会是素数。

所以除了 $2$ 和 $3$ ，所有素数都会是 $6$ 的倍数加 $1$ 或减 $1$ 。

阿贝多看砂糖分析的头头是道，决定给她出道题。题目很简单，给定若干个整数区间 a ∼ b ，求这些区间中素数的数量，当然计算素数数量的时候重复的算一个，只有你能帮助砂糖了。

输入

第一行一个整数 $N$ ($1 ≤ N ≤ 1000$)，表示 $N$ 个区间接下来 $N$ 行，每行有两个整数 $a$ , $b$ ($1 ≤ a,b ≤ 10^5$)， 分别表示区间 a∼b。

输出

输出所有区间中，素数的数量（重复的素数只计算一次）

样例输入1

1
1 4

样例输出1

2

样例输入2

2
5 7
7 9

样例输出2

2