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
rexx: 2018-10-16 19:58:30

very nice problem :)

darkknight21: 2018-09-10 19:09:01

solvable using inclusion-exclusion principle take care of implementation

dunjen_master: 2017-09-01 00:29:27

tle by iteration..

kejriwal: 2016-02-01 12:05:01

easy math :)

syukri: 2015-10-29 06:02:54

got TLE :-)

Sonu Sharma: 2015-10-27 13:07:51

Take special care of :n & m (inclusive) <<<<<not>>>>> divisible by

arpita: 2015-09-27 20:03:42

anyone had its correct ans? plz comment ur id,

arpita: 2015-09-27 19:03:43

Last edit: 2015-09-27 19:58:02
varun yadav: 2015-09-27 09:37:23

my solution is showing WA,, what should i do ??? link ----> http://ideone.com/yAVncM

Abhinav: 2015-01-07 17:52:44

getting WA at 9th case any tricky case ?


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