Master Zhu 曾经提出了以下数学问题：

给定四个整数 $A, B, C$ 和 $D$，有多少个不同的整数四元组 $(a, b, c, d)$ 满足以下所有条件：

$$ \begin{aligned} a + c &> b + d \\ a + d &\geq b + c \\ 0 &\leq a \leq A \\ 0 &\leq b \leq B \\ 0 &\leq c \leq C \\ 0 &\leq d \leq D \end{aligned} $$

请求出满足条件的四元组数量。由于答案可能非常大，你只需要计算其对 $10^9 + 7$ 取模的结果。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \leq T \leq 1000$)。

每个测试用例占一行，包含四个整数 $A, B, C$ 和 $D$ ($0 \leq A, B, C, D \leq 10^{18}$)。

输出格式

对于每个测试用例，输出一行，包含一个整数，即答案对 $10^9 + 7$ 取模的结果。

样例

输入 1

1
2 1 1 1

输出 1

10