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
2014-07-27 16:27:42 Hussain
Very nice problem
2014-05-19 10:10:30 excursionist
@vijay:= ur count variable containts old value update it to 0 after printing it for each test case
2014-05-17 12:28:17 pvkcse
Any tricky case please...getting o/p in ideone but here it is WA... <snip>

Last edit: 2023-05-18 20:38:00
2014-02-21 16:50:43 785227
Please check my submission ID 11100462
Getting WA again and again
2013-07-30 18:43:15 pranjuldb
nice question... :)
2013-06-01 15:24:21 Aayush Agarwal
@DEVIL D : the answer for the first test case should be 10 because it is said which are not divisible by a or a+d or a+2d.... so numbers upto 9 are not divisible by 10 and 10 is not divisible by 6 or 8 or 4.. so every number is counted in this manner.

Last edit: 2013-06-01 15:25:22
2012-07-29 13:04:43 Saurabh Jain
@Devil D: i have checked a lot of test cases correctly on my system but here i'm getting WA.... could you please tell me reason for the same or test case for which my algo fails?
2012-07-01 05:51:45 Abhishek Mishra
i think there is no test case for any extreme one..;)
2012-06-05 04:22:24 Better late than never !!!
It's not at all easy :O
2012-06-01 14:43:33 Ravi kishore
Nice problem!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.