Description

After fz retired, he started studying regular school courses.

fz encountered a problem like this:

Given intervals $[a, b]$ and $[c, d]$, pick one integer from each interval uniformly at random, and find the probability that their sum equals $e$.

fz originally wanted to change "equals $e$" into "$\in [e,f]$", but then he would become one of those annoying problem setters who rely on messy case discussions, so he decided not to change it.

For convenience, you only need to output the value of the answer multiplied by $(b-a+1)(d-c+1)$. It can be proven that this number is an integer.

Input Format

The first line contains an integer $T$, meaning there are $T$ test cases.

In the next $T$ lines, each line contains five integers $a, b, c, d, e$.

Output Format

Output $T$ lines. For each test case, output one non-negative integer, representing the corresponding answer.

1
1 2 3 4 5

2

Hint

Sample explanation:

For the first test case in the sample, there are $4$ ways to randomly choose one integer from $[1,2]$ and one integer from $[3,4]$. Only $\{1,4\}$ and $\{2,3\}$ have sum $5$, so the probability is $\dfrac12$.

Let $N=\max\{|a|,|b|,|c|,|d|,|e|\}$.

Constraints for all testdata:

• $1 \le T \le 1000$.
• $0 \le N \le 10^{18}$.

This problem does not use bundled tests.

• Idea: FZzzz
• Solution: FZzzz
• Code: FZzzz
• Data: FZzzz

Translated by ChatGPT 5