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

题目描述

爆爆龙大军压境，身为 龙族最聪明的龙——奶龙为了对付爆爆龙,决定使用一种古老的魔法.

为了完成对魔法的引导，需要走 m 道 流程.

对于每一个流程，需要根据这个流程所给的$l,r$,求出 $[l,r]$ 范围内的质数之和.(其中 $1 \le l \le r$)

(质数指的是大于 $1$ 的正整数，并且只能被 $1$ 和它本身整除的数.)

但 奶龙 很懒，不想自己算，于是他找到了你，希望你帮他算一下。

输入格式

第一行输入一个整数 $m (1 \le m \le 10^5)$

接下来 $m$ 行,每行输入两个整数 $l,r(1 \le l \le r \le 10^6)$ 也就是询问 $[l,r]$ 范围内的质数之和

输出格式

对于每一个询问，输出一行一个整数，代表答案。

样例

2
2 11
14 16

28
0

样例解释

$[2,11]$ 范围内的质数有 $2,3,5,7,11$ ,它们的和为 $2+3+5+7+11=28$ $[14,16]$ 范围内没有质数，所以和为 $0$

数据范围

对于 $30\%$ 的数据, $1 \le m \le 5000,1 \le l \le r \le 10^4$

对于 $100\%$ 的数据, $1 \le m \le 10^5,1 \le l \le r \le 10^6$