Due to COVID19 all employees of chemical factory are quarantined in home. So, company is organized by automated robots. There are $N$ Containers in company, which are labelled with $1$ to $N$ numbers. There are Total $N$ robots in Company, which are labelled $1$ to $N$. 
Each Robot adds $1$ litter Chemical in containers whose labels are multiple of robots’ label. (E.g. robot labelled 2 will add Chemical in containers labelled 2, 4, 6, ….). 
Robots follow few rules mentioned below:
- Chemical with $pH<7$ is acidic.
- Chemical with $pH=7$ is neutral.
- Chemical with $pH>7$ is basic.
- Mixture of $1$ litter acid and $1$ litter base makes neutral solution.
- If Container is empty or pH of Chemical in container is equal to 
- $7$ then robot adds $1$ litter acidic Chemical.
- If pH of Chemical in container is less than $7$ then robots adds $1$ litter basic Chemical.
Now Chemical is packed in $4$ ways:
- Containers with exactly $2$ litter acid and $1$ litter base are packed at $P1$ cost. 
- Containers with acidic Chemical are packed at $P2$ cost. (Here Don’t consider containers with exactly $2$ litter acid and $1$ litter base as we counted them in above rule)
- Containers with $pH=7$ Chemical is packed at $P3$ cost.
- Containers with Basic Chemical are packed at $P4$ cost.
Now $1$ employee given task to find packing cost of containers with labels in range $[ k1, k2]$ (Inclusive). Help him out. As Cost can be large find cost in modulo of $100000007$

-----Input:-----
- The first line of the input contains a single integer T denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains $3$ space separated Integers $N$, $K1$ and $K2$.
- The second and last line contains $4$ space separated Integers $P1$, $P2$, $P3$ and $P4$

-----Output:-----
For each test case, print total cost of packing of containers modulo 100000007.

-----Constraints-----
- $1 \leq T \leq 50000$
- $1 \leq P1, P2, P3, P4 \leq 2*10^7$
- $2 \leq N \leq 2*10^7$
- $1 \leq K1, K2 \leq N$

-----Subtasks-----Subtask #1 (20 points):
- $1 \leq T \leq 10$
- $1 \leq P1, P2, P3, P4 \leq 2*10^7$
- $2 \leq N \leq 1000$
- $1 \leq K1, K2 \leq N$Subtask #2 (80 points) :
- Original Constraint

-----Sample Input:-----
1
4 1 4
2 2 2 2

-----Sample Output:-----
8

-----Explanation:-----
Let’s use notation, 
0 for acidic Chemical, 
1 for Chemical with pH=7, 
2 for basic Chemical,
3 for Containers with exactly 2 litter acid and 1 litter base,
-1 for empty containers
Initially 4 containers are empty so
[-1, -1, -1, -1]
Robot 1 adds 1 litter acid in all containers.
[0, 0, 0, 0]
Robot 2 adds base in containers labelled 2, 4
[0, 1, 0, 1]
Robot 3 adds base in containers labelled 3
[0, 1, 1, 1]
Robot 4 adds acid in containers labelled 4 because it contains Chemical with pH=7. After adding acid, it also contains exactly 2 litter acid and 1 litter base, so denoting it with 3.
[0, 1, 1, 3]
Corresponding cost of packing container
[P2, P3, P3, P1]
Now, calculate total cost,
Cost = P2+P3+P3+P1 = 2+2+2+2 = 8

```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 = 'import atexit\nimport io\nimport sys\nimport math\nfrom collections import defaultdict,Counter\n\n_INPUT_LINES = sys.stdin.read().splitlines()\ninput = iter(_INPUT_LINES).__next__\n_OUTPUT_BUFFER = io.StringIO()\nsys.stdout = _OUTPUT_BUFFER\n\n@atexit.register\ndef write():\n    sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())\n\n# dp=[0]*(2*pow(10,7)+1)\n# for i in range(1,2*pow(10,7)+1):\n#     d=int(math.sqrt(i))\n#     if d*d==i:\n#         c=0\n#         for j in range(2,int(math.sqrt(d))+1):\n#             if d%j==0:\n#                 c=1\n#                 break\n                \n#         if c==0:\n#             dp[i]=3\n#         else:\n#             dp[i]=0\n#     else:\n#         dp[i]=1\n        \n# n0=[0]*(2*pow(10,7)+1)\n# n1=[0]*(2*pow(10,7)+1)\n# n3=[0]*(2*pow(10,7)+1)\n# for i in range(1,2*pow(10,7)+1):\n#     if dp[i]==0:\n#         n0[i]=1\n#     elif dp[i]==1:\n#         n1[i]=1\n#     else:\n#         n3[i]=1\n#     n0[i]+=n0[i-1]\n#     n1[i]+=n1[i-1]\n#     n3[i]+=n3[i-1]\ndef isprime(d):\n    for j in range(2,int(math.sqrt(d))+1):\n        if d%j==0:\n            return False\n    return True\n          \nm=100000007\nt=int(input())\nfor i in range(t):\n    n,k1,k2=list(map(int,input().split()))\n    p1,p2,p3,p4=list(map(int,input().split()))\n    p=int(math.sqrt(k1))\n    if p*p<k1:\n        p+=1\n    c=0\n    ans=0\n    while p*p<=k2:\n        c+=1\n        if isprime(p):\n            ans=(ans+p1)%m\n        else:\n            ans=(ans+p2)%m\n        p+=1\n    ans=(ans+(p3*(k2-k1+1-c))%m)%m\n    print(ans)\n'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 22850