Description

Recently, Gilgamesh found that he's almost lack of swords in his vault, so he wants to forge a lot of swords with different shapes. He command you to forge for him!

Gilgamesh's sword can only be forged by triangle. Different triangle can be forged into a unique sword. He will give you the intervals of the edges of triangles, you have to calculate how many swords with different shape can he get?

Gilgamesh threats you with his "Gate of Babylon".

---

You are given four positive integer $A\le B\le C\le D$, you're going to count how many triangle that can be build by edges with length $x,\ y,\ z$, where $A\le x\le B,\ B\le y\le C,\ C\le z\le D$.

For example: $A=1,\ B=2,\ C=3,\ D=4$

You can build triangles with edges : $(x,y,z)\in \{(1,3,3),\ (2,2,3),\ (2,3,3),\ (2,3,4)\}$.

So the answer is 4.

Input

The first line contains one integer $T$, there are $T$ testcases below.

For each testcase, the four integer $A,\ B,\ C,\ D$ is given respectively.

$1\le T\le 100$.

$1\le A\le B\le C\le D\le 5\times 10^4$.

Output

For each testcase, output its answer, followed by a newline character.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss