PUPER_FUSED

3.5

49 votes
Easy
Problem

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

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

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

Editor Image

?