HASH  Hashing
Consider the hash function h(y) = a*y + b (mod m) which maps each integer to some integer between 0 and m1. You are given x,n,c,d and are curious how many of the hash values h(x),h(x+1),...,h(x+n) land in the interval [c,d].
Input
The first line contains a positive integer t, the number of test cases (1 ≤ t ≤ 10^5). t lines then follow, where the ith line gives the values a,b,x,n,c,d,m, spaceseparated, for the ith test case. All given values are nonnegative. Also, 1 ≤ m ≤ 10^{15}, c ≤ d < m, a,b < m, x+n ≤ 10^{15}, and a*(x+n) + b ≤ 10^{15}.
Output
For each test case in order output the number of i, 0 ≤ i ≤ n, such that c ≤ a*(x+i) + b (mod m) ≤ d in that test case, followed by a newline.
Example
Input: 2 2 3 1 3 0 1 7 1 0 0 8 0 8 9 Output: 1 9
hide comments
arthurcrs:
20180827 00:32:01
A better example:


otacilion:
20180820 16:47:01
Can someone send more examples of inputs and outputs? 

hodobox:
20170505 16:37:04
In the first case, a*(x+1)+b = 2*(1+1)+3 = 4+3 = 0 (mod 7), which is in the interval [0,1] 

givemered:
20160120 21:15:05
Even i think it must be ZERO. 

karthik1997:
20150816 19:21:46
please check if there is error in the first output .it must be zero according to the above constraints 
Added by:  Minilek 
Date:  20081222 
Time limit:  3.609s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  MIT Individual Contest 2008 