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
pranjuldb: 2013-07-30 18:43:15

nice question... :)

Aayush Agarwal: 2013-06-01 15:24:21

@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
Saurabh Jain: 2012-07-29 13:04:43

@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?

Abhishek Mishra: 2012-07-01 05:51:45

i think there is no test case for any extreme one..;)

Better late than never !!!: 2012-06-05 04:22:24

It's not at all easy :O

Ravi kishore : 2012-06-01 14:43:33

Nice problem!

Carlos Aponte: 2012-05-25 16:31:35

May anyone help me see the error in my answer 6936482

Thank you.

Aman Kumar: 2012-05-10 11:32:42

inclusion exclusion :)

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

@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
Pranay: 2012-04-24 06:30:12

Last edit: 2012-11-07 17:39:56

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