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

ayushi agarwal: 2014-11-18 13:39:31

why unsigned int doesn't work and long long int work in c++

Hussain: 2014-07-27 16:27:42

Very nice problem

excursionist: 2014-05-19 10:10:30

@vijay:= ur count variable containts old value update it to 0 after printing it for each test case

pvkcse: 2014-05-17 12:28:17

Any tricky case please...getting o/p in ideone but here it is WA... http://ideone.com/spdZlb

785227: 2014-02-21 16:50:43

Please check my submission ID 11100462
Getting WA again and again


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