EASYMATH - EASY MATH

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^32

1 <= a <= 2^32

1 <= d <= 2^32

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 www.spoj.com/problems/EASYMATC/


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

hide comments
2012-05-10 11:32:42 Aman Kumar
inclusion exclusion :)
2012-04-24 06:30:12 Gaurav
@devil D could you please see my soln and tell why it is giving WA...

-----
Failing for large numbers

Last edit: 2012-05-09 12:45:06
2012-04-24 06:30:12 (Tjandra Satria Gunawan)(曾毅昆)
Nice problem ;)
2012-04-24 06:30:12 Francky
Nice problem, tutorial edition is Euler001 ;-)

Last edit: 2012-04-17 20:33:25
2012-04-24 06:30:12 Devil D
Sorry again
its 1 10 2 2
2012-04-24 06:30:12 mehmetin
m = 20 in the first test case.

Last edit: 2012-04-17 12:59:19
2012-04-24 06:30:12 Devil D
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
2012-04-24 06:30:12 Devil D
Sorry and thanks..
Changed the problem statement
2012-04-24 06:30:12 __AAA__
what is the purpose of a?
and could you please explain first test case as every number is divisible by 1?
2012-04-24 06:30:12 Ikhaduri
What's "a" for???
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.