EASYMATH - EASY MATH

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/


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

hide comments
2023-07-27 06:31:03
meh math math and math @@
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
2022-01-25 15:15:03
Made this editorial, and linked a few other resources https://youtu.be/2TijUJXvyGw
2021-07-01 08:09:22
how to handle overflow when calculating LCM of numbers
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.
2020-06-21 07:01:30
OMG, it is all about Math.
got my AC in 5 tries :(((
2020-06-17 21:33:30
AC. YAY. Inclusion exclusion saved this
2020-05-01 11:28:10
can anyone give a hint
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
2019-06-20 15:08:47
Find the pattern between inclusion exclusion formula and subsets of a set. Then implement it
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.