一天winterzz1将自己的大脑的思维方式改成了任意进制，他的大脑可以以任意进制下思考问题，甚至在二进制模式下拥有不亚于计算机的计算能力。于是他注意到了一个问题在A进制下的L1到R1区间内和B进制下L2到R2区间内，有多少数字字面相同。字面相同的意思就是看起来一样。比如3进制下1到12之间有五个数分别是1，2，10，11，12，然后10进制下2到11之间有10个数分别是2，3，4，5，6，7，8，9，10，11。然后在两种进制的两个区间内，字面相同的有三个数分别是2,10,11。因此对于这种情况，3就是我们所求的答案。
输入描述:
首先输入一个T，表示T组案例（T<=100000），每组案例首先输入一行两个数A,B，表示两个进制2<=A,B<=10，然后输入两行，每行两个在相应进制下的整数，分别代表该进制下L1，R1，L2，R2。
这四个整数的每个整数都满足最多18位，也就是这四个整数的每个整数变成字符串之后的长度<=18
输出描述:
对于每组案例，输出答案表示有多少数字字面相同。
示例1
说明
3进制下的2（其值等于10下的2）与10进制下的2字面相同。
3进制下的10（其值等于10下的4）与10进制下的10字面相同。
备注:
字面相同的含义为：将其输出为字符串，两字符串相同。