Description

After obtaining enough swords, Gilgamesh would like to forge some more swords in his favorite form.

The requirements of forging a sword is to build a valid triangle: $x+y>z\text{ where }x, y, z\text{ is the sides}$. However, Gilgamesh prefers swords that forged by one more constrain: $x+y<1.5z$.

Now, he threats you with more swords that you forged, you have to help him.

---

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

A eligible triangle should follow the following condition:

1. $x+y>z$
2. $x+y<1.5z$

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,4)\}$

So the answer is 3.

• Note that although $(2,3,3)$ is a valid triangle, it does not fit the 2-nd constrain: $x+y<1.5z$ ($2+3=5>1.5\times 3=4.5$).

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

Discuss