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
meryx: 2019-11-01 01:09:19

I keep getting TLE :(
I think my solution is efficient enough, used inclusion exclusion etc but I just keep getting TLE
wish I could see others solutions

hrittik16: 2019-06-20 15:08:47

Find the pattern between inclusion exclusion formula and subsets of a set. Then implement it

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

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