Problem Description

Xiao Lan found an interesting sequence. The first few terms are as follows:

$1,1,2,1,2,3,1,2,3,4,\ldots$

Xiao Lan noticed that the first $1$ term of this sequence is the integer $1$. The next $2$ terms are the integers from $1$ to $2$. The next $3$ terms are the integers from $1$ to $3$. The next $4$ terms are the integers from $1$ to $4$, and so on.

Xiao Lan wants to know the sum of a consecutive segment in this sequence.

Input Format

The first line contains an integer $T$, which indicates the number of queries.

The next $T$ lines each contain one query. In the $i$-th line, there are two integers $l_{i}$ and $r_{i}$, meaning the query asks for the sum from the $l_{i}$-th number to the $r_{i}$-th number in the sequence.

Output Format

Output $T$ lines. Each line contains one integer representing the answer to the corresponding query.

3
1 1
1 3
5 8

1
4
8

Hint

For $10\%$ of the testdata, $1 \leq T \leq 30$, $1 \leq l_{i} \leq r_{i} \leq 100$.

For $20\%$ of the testdata, $1 \leq T \leq 100$, $1 \leq l_{i} \leq r_{i} \leq 1000$.

For $40\%$ of the testdata, $1 \leq T \leq 1000$, $1 \leq l_{i} \leq r_{i} \leq 10^{6}$.

For $70\%$ of the testdata, $1 \leq T \leq 10000$, $1 \leq l_{i} \leq r_{i} \leq 10^{9}$.

For $80\%$ of the testdata, $1 \leq T \leq 1000$, $1 \leq l_{i} \leq r_{i} \leq 10^{12}$.

For $90\%$ of the testdata, $1 \leq T \leq 10000$, $1 \leq l_{i} \leq r_{i} \leq 10^{12}$.

For all testdata, $1 \leq T \leq 100000$, $1 \leq l_{i} \leq r_{i} \leq 10^{12}$.

Lanqiao Cup 2021 National Contest Group A Problem E (Group B Problem F, Group C Problem F).

Translated by ChatGPT 5