[Codejam2010]Number Game

时间限制:10s      空间限制:128MB

题目描述

xlb和blx在玩一个游戏:有A和B两个数字,两人轮流对他们进行如下操作:可以A替换成A-k*B或者将B替换成B-k*A(k是任意正整数),谁让其中一个数替换为0或者小于0,那么他就输了。
对于两个数A,B开始的游戏,如果xlb先进行操作,他有办法让blx无论如何操作,自己都赢得游戏,那么我们称游戏(A,B)为必胜游戏。
给你整数A1,A2,B1,B2,要求统计出有多少个游戏(A,B)(A1<=A<=A2,B1<=B<=B2)是必胜游戏。
 


输入格式

第一行一个整数T,数据组数
接下来T行,每行4个正整数A1,A2,B1,B2
 


输出格式

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


样例输入

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

样例输出

1
20
0
 

提示

没有写明提示


题目来源

没有写明来源