暖鸭
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

还记得什么是阶乘吗，现在不考这个...
问给定  T 组数据，每组数据给定 l,r
在所有的l\le a \le b \le r 中，等可能地随机取一对(a, b)
求区间 [a, b] 至少包含一个平方数的概率
为了计算方便，最终答案乘上 (r-l+1)*(r-l+2) 后对 1000000007取模

输入描述:

第一行输入一个 T，表示  T 组数据
接下来每行一组 l,r 如题所示
1\le T \le 3 × 10^5; 1 \le l \le r \le 1 × 10^{16}

输出描述:

输出一个非负整数表示最终答案
示例1

输入

复制 
3
1 1
1 2
1 3

输出

复制 
2
4
6

说明

[1,2] 中 a,b 有 [1,1], [1, 2], [2, 2]三种等可能区间，仅仅 [2, 2]没有包含完全平方数1
故答案为 2/3
输出 (2/3 * 3 * 2)%(1e9+7) = 4
示例2

输入

复制 
1
3 5

输出

复制 
8

备注:

1000000007 = 1×10^9+7 是个质数

本题输入量较大，请使用较快的读入方式