## HASH - Hashing

no tags

Consider the hash function h(y) = a*y + b (mod m) which maps each integer to some integer between 0 and m-1. 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, space-separated, for the ith test case. All given values are non-negative. Also, 1 ≤ m ≤ 1015, c ≤ d < m, a,b < m, x+n ≤ 1015, and a*(x+n) + b ≤ 1015.

### 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
``` arthurcrs: 2018-08-27 00:32:01 A better example: Input: 2 3014430 0 0 557 1225689 2597995 6928569 161828 0 0 383 100002 6847833 7198785 Output: 112 359 otacilion: 2018-08-20 16:47:01 Can someone send more examples of inputs and outputs? hodobox: 2017-05-05 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: 2016-01-20 21:15:05 Even i think it must be ZERO. karthik1997: 2015-08-16 19:21:46 please check if there is error in the first output .it must be zero according to the above constraints