You will be given 4 numbers: n m a d.

Find count of numbers between n and m (inclusive) not divisible by (a) or (a+d) or (a+2d) or (a+3d) or (a+4d).

Input

First line has number t - number of test cases.

Each test case has 4 numbers n m a d.

Output

Single line having single number giving the count.

Constraints

1 ≤ n ≤ m ≤ 2³²

1 ≤ a ≤ 2³²

1 ≤ d ≤ 2³²

2 ≤ t ≤ 100

Example

Input:
3
1 10 2 2
20 100 3 3
100 1000 4 5
Output:
5
54
543

Also try the challenge version at EASYMATC