Sequence

Consider the infinite sequence:

A=1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, 1, 2,...

which is formed by writing the vectors $1,\ldots,n$ side by side for every $n=1,2,3,4,...$. Peter’s task is to calculate the sum $A_{lo}+A_{lo+1}+\ldots+A_{up}$ for any given positive integers $lo\le up$. Let’s help him write the code!

Input specification

The first line contains the number of queries, $Q$. This is followed by $Q$ lines, each containing two numbers for which the requested sum needs to be determined. The numbers on each line are separated by a space.

Output specification

$Q$ lines with answer for the queries. We can be certain that the answers will fit within a 64-bit signed integer.

Constraints

$1\le Q \le 1\_000$
$1\le lo\le up \le 10\_000\_000\_000$

Sample input 1

1. 3
2. 1 3
3. 4 13
4. 14 23

download as text file

Sample output 1

1. 4
2. 22
3. 33

download as text file

Sample input 2

1. 3
2. 1 101
3. 2 10001
4. 3 100001

download as text file

Sample output 2

1. 510
2. 475825
3. 14937054

download as text file