D. Yet Another Math Query Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Janma and Tascantos were talking with Tusianoli about another math query problem:

There are $$$q$$$ queries of the form $$$(l, r, x)$$$, and for each query you have to output the number of pairs of integers $$$(a, b)$$$ where $$$l \leq a \leq b \leq r$$$ and $$$f(a, b) = x$$$.

$$$f(a, b) = a + b + |a - b|$$$ where $$$|a-b|$$$ means absolute value of $$$a-b$$$.

Please help them to solve the problem.

Input

The first line consists in one integer $$$q$$$ $$$(1 \leq q \leq 2 \cdot 10^{5})$$$ — the number of queries.

Then follows $$$q$$$ lines with with three integers $$$(l, r, x)$$$. $$$(1 \leq l \leq r \leq 10^{18})$$$, $$$(1 \leq x \leq 10^{18})$$$ — the values previously described at the statement.

—

Testcases in subtasks are numbered from $$$1$$$ to $$$20$$$ with samples skipped.

Test $$$1$$$: $$$(q = 1)$$$ and $$$(1 \leq l \leq r \leq 1000)$$$.

Tests $$$2-20$$$: No additional constraints.

Each test is worth 5 points with samples skipped.

Output

Output the number of pairs for each query.

Example
Input
2
2 6 8
3 9 5
Output
3
0
Note

All possible pairs for the first query are: $$$(2, 4)$$$, $$$(3, 4)$$$ and $$$(4, 4)$$$

There are not suitable pairs for the second query.

 —

Problem Idea: danx

Problem Preparation: danx

Occurrences: Novice 4