本题与简单版本的唯一区别是  本题带有多组询问，需要快速回答出每次询问的答案

存在一个从1,2,3,4,5....n的序列，n=1e9，给出一个询问区间[l,r]，请你求出sqrt(l)+sqrt(l+1)+sqrt(l+2)...+sqrt(r-1)+sqrt(r)的值。(此处sqrt(i)表示根号i向下取整)

由于数据范围较大，请使用高效的计算方法。

第一行输入一个整数T(T<=2e5)，表示有T组样例

接下来T行每行两个正整数l,r(l<=r&&r<=1e9)表示询问区间[l,r]。