题目描述

定义一类新型数字 $Z$，当且仅当一个数字的因数个数大于$2$且这个数字不被$2$整除时，这个数字属于$Z$。 例如，$4$有三个因数：$1$，$2$，$4$，但是$4\\%2=0$，所以$4$不是$Z$，$9$有三个因数：$1$，$3$，$9$，$9\\%2=1$，所以$9$是$Z$。 给定$q$次询问，每次询问给定一组$l$，$r$，请回答区间$[l$，$r]$内所有$Z$的和是多少，即$∑_{i=l}^{r}i(i∈Z)$

输入格式

第一行一个整数$q$，表示$q$次询问 接下来$q$行，每行两个数分别为$l$和$r$。 $1 \\leq l \\leq r \\leq 10^6$

$1 \\leq q \\leq 10^6$

输出格式

输出$q$行，每行一个数字表示该次询问的答案

样例

3 
1 10 
11 15 
16 30

9 
15 
73

提示

by 励翔 2022春第二次排位赛