### 问题描述

素数（也称为质数）的定义是：若该数不能被除 $1$ 和本身之外的其他数整除，则该数为素数，否则为合数。

$1$ 既不是质数也不是合数。

素数的例子（$100$ 以内有 $25$ 个素数）：$2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97$。

合数的例子：$8, 9, 10, 15$。

在本题中，输入两个正整数 $n$ 和 $m(1\le n\le m\le 10^9,m-n\le 10^6)$，需要查询 $[n, m]$ 范围所有质数的和。

输入格式

输入数据第 $1$ 行为正整数 $T$，表示查询的个数，$2≤T≤100$。

每个查询占一行，为 $2$ 个正整数，$n, m(1\le n\le m\le 10^9,m-n\le 10^6)$。

输出格式

对每个查询，输出占一行，为一个正整数，表示求得的答案。

输入样例

1
1 100

输出样例

1060