You will be given 4 numbers

n m a d

find count of numbers between n & 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

Example

Input:
3

1 10 2 2

20 100 3 3

100 1000 4 5 
Output:

5

54

543

NOTE - 1<=n<=m<= 2^32

	1<=a<= 2^32

	1<=d<=2^32

	2<=t<=100

ALSO TRY THR CHALLENGE VERSION --- /http://www.spoj.com/problems/EASYMATC/