Once Puper was studying in his class and he was feeling bored from the teachers lecture, and teacher knows this fact.
So to insult Puper teacher ask him a question which teacher thinks Puper cannot answer but he don't know the geekiness of Puper.
Teacher gives him a range [L,R] and ask for the sum of all the difference of square of two consecutive non intersecting paired numbers from L to R. i.e. [L+1,L] is one pair , [L+3,L+2] is another and so on till R and if any number is left unpaired at the last then simply square it and add it to the sum value.
(Non intersecting in terms of position of a number in a given range L to R).
So help Puper in escaping this situation. Print the answer modulo 1000000007.
INPUT:-
First line contains the T the no. of test case. Next T lines contains the ranges [L,R]
OUTPUT
Corresponding to each test case output the value of the in the given range.
Example:- For L=1 , R=4 , you need to find 2^2-1^2+4^2-3^2.
CONSTRAINTS
T<=10^6
1<=L<=R<=10^18
In test case 1
we have L=1 and R=3
so pairs so formed are (1,2) and 3 itself as it is left unpaired.
so sum=3+9=12
which is the required answer