Its Christmas time and Santa has started his ride to deliver gifts to children waiting for him in a 1-dimentional city. All houses in this city are on a number line numbered as 1, 2, 3… and so on. Santa wants to deliver to houses from n to m, but he found that all the kids living at positions that are divisible by a, a+d, a+2d, a+3d or a+4d are naughty and he does not want to deliver them any gifts. Santa wants to know how many gifts he has to carry before leaving to the city given that there is only one kid in a house. Help him out!
Formally, Given $m, n, a, d \in \mathbb{N}$ where $n < m$, find the number of $x \in \{n, n+1, ..., m-1, m\}$ such that $x$ is not divisible by $a$, $a+d$, $a+2d$, $a+3d$ or $a+4d$

-----Input-----
The first line is the number $t$, corresponding to number of test cases\
This is followed by $t$ lines of the format: $n$ $m$ $a$ $d$

-----Output-----
For each test case, print a single number that is the number of gifts Santa should pack.

-----Constraints-----
- $1 < m, n, a \leq 2^{32}$
- $1 < d \leq 2^{10}$

-----Sample Input:-----
1
2 20 2 1

-----Sample Output:-----
5

-----Explanation:-----
In the range {2, 3, 4, …, 19, 20}, only {7, 11, 13, 17, 19} are not divisible by 2, 3, 4, 5, or 6

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'from math import gcd\r\nfrom math import ceil\r\nfrom itertools import combinations as c\r\nt=int(input())\r\nfor _ in range(t):\r\n    n,m,a,d=list(map(int,input().split()))\r\n    \r\n    l=[]\r\n    for i in range(5):\r\n        l.append(a+i*d)\r\n    ans=m-n+1\r\n    for i in range(1,6):\r\n        x=list(c(l,i))\r\n        for j in x:\r\n            e=j[0]\r\n            for v in j:\r\n                e=(e*v)//gcd(e,v)\r\n            #print(e)\r\n            if i%2:\r\n                ans-=m//e-(n-1)//e\r\n            else:\r\n                ans+=m//e-(n-1)//e\r\n    print(ans)\r\n        \r\n    \r\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13301