EASYMATH - EASY MATH

no tags 

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/


hide comments
krytal: 2023-07-27 06:31:03

meh math math and math @@

creed_667: 2022-08-28 23:03:15

If you're looking for English editorial, I have written the whole explanation on this article in English:
<snip>
[Simes]: No thanks, we don't want links to solutions.

Last edit: 2022-08-29 07:11:35
fatahchan: 2022-01-25 15:15:03

Made this editorial, and linked a few other resources https://youtu.be/2TijUJXvyGw

coding_lord: 2021-07-01 08:09:22

how to handle overflow when calculating LCM of numbers

unexh_21: 2021-01-20 20:34:07

finally got it, in one go, but learnt a lot of applied theory in meanwhile. If anyone want to know method, learn inclusion-exclusion with bit-masking.

abdo_farah: 2020-06-21 07:01:30

OMG, it is all about Math.
got my AC in 5 tries :(((

siddhantj19: 2020-06-17 21:33:30

AC. YAY. Inclusion exclusion saved this

adityaguptagkp: 2020-05-01 11:28:10

can anyone give a hint

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


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