扩展欧几里得3

题目描述

输入$T$，一共$T$组数据，每组三个数$a, b, d, l_1, r_1, l_2, r_2$，输出$ax+by=d$有多少个解$(x, y)$满足$l_1\leq x\leq r_1, l_2\leq y\leq r_2$。

输入格式

第一行一个数字$T$。

接下来$T$行，每行三个数字$a, b, d, l_1, r_1, l_2, r_2$。

输出格式

一共$T$行，每行一个数表示答案。

样例输入

3
1 2 5 0 10 0 10
100 150 1000 -10 0 0 10
3 2 1 0 100 0 100

样例输出

3
2
0

数据范围

对于$100\%$的数据，保证$1\leq T\leq 10^4, 1\leq a, b\leq 10^9, 1\leq d\leq 10^{18}, -10^{18}\leq l_1\leq r_1\leq 10^{18}, -10^{18}\leq l_2\leq r_2\leq 10^{18}$。