504034 - 解的个数

【题目描述】解的个数(ans)

已知整数x,y满足ax+by+c=0(p≤x≤q,r≤y≤s),求满足这些条件的x,y的个数。

Input

第一行有一个整数n(n≤10),表示有n个任务。 以下有n行,每行有7个整数,分别为a,b,c,p,q,r,s,均不超过10^8

Output

共n行,第i行是第i个任务的解的个数。

Examples

Input

2
2 3 -7 0 10 0 10
1 1 1 -10 10 -9 9

Output

1
19
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题