题目描述

xlb 和 blx 在玩一个游戏：有 $A$ 和 $B$ 两个数字，两人轮流对他们进行如下操作：可以 $A$ 替换成 $A-k\times B$ 或者将 $B$ 替换成 $B-k\times A$（ $k$ 是任意正整数），谁让其中一个数替换为 $0$ 或者小于 $0$，那么他就输了。

对于两个数 $A,B$ 开始的游戏，如果 xlb 先进行操作，他有办法让 blx 无论如何操作，自己都赢得游戏，那么我们称游戏 $(A,B)$ 为必胜游戏。

给你整数 $A_1,A_2,B_1,B_2$，要求统计出有多少个游戏 $(A,B)$ 满足 （$A_1\leq A\leq A_2$，$B_1\leq B\leq B_2$） 且是必胜游戏。

输入格式

第一行一个整数 $T$，表示数据组数。
接下来 $T$ 行，每行 $4$ 个正整数 $A_1,A_2,B_1,B_2$。

输出格式

$T$ 行，每行对输出一组数据的必胜游戏的个数。

3
2 2 11 11
1 6 1 6
8 8 5 5

1
20
0

数据规模与约定

对于 $100\%$ 的数据，$T\leq 100$，$1\leq A_1,A_2,B_1,B_2\leq 10^6$。