EASYMATH - EASY MATH

no tags 

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/

hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2012-04-24 06:30:12

Nice problem ;)

Legend Wait For It :D: 2012-04-24 06:30:12

Last edit: 2013-09-22 16:00:04
Francky: 2012-04-24 06:30:12

Nice problem, tutorial edition is Euler001 ;-)

Last edit: 2012-04-17 20:33:25
Devil D: 2012-04-24 06:30:12

Sorry again
its 1 10 2 2

mehmetin: 2012-04-24 06:30:12

m = 20 in the first test case.

Last edit: 2012-04-17 12:59:19
Devil D: 2012-04-24 06:30:12

For the first test case the numbers are
1 2 3 4 5 6 7 8 9 10.
...
Only 1 3 5 7 9
are not divisible by 2 4 6 8 10

Devil D: 2012-04-24 06:30:12

Sorry and thanks..
Changed the problem statement

__AAA__: 2012-04-24 06:30:12

what is the purpose of a?
and could you please explain first test case as every number is divisible by 1?

Ikhaduri: 2012-04-24 06:30:12

What's "a" for???

mehmetin: 2012-04-24 06:30:12

I think there is an error in the problem statement. Input "a" is not used and result for first test case seems to be wrong.

Last edit: 2012-04-17 10:51:00

Added by:Devil D
Date:2012-04-17
Time limit:0.100s-1s
Source limit:20000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own