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

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
T = int(input())
for _ in range(T):
	(N, K1, K2) = list(map(int, input().split()))
	(P1, P2, P3, P4) = list(map(int, input().split()))
	ans = 0
	arr = [0] * 1005
	length = len(arr)
	for i in range(1, N + 1):
		j = 0
		while j < length:
			arr[j] += 1
			j += i
	for i in range(K1, K2 + 1):
		if arr[i] == 3:
			ans += P1
		elif arr[i] % 2 == 1:
			ans += P2
		else:
			ans += P3
	print(ans)


import atexit
import io
import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')

def isprime(d):
	for j in range(2, int(math.sqrt(d)) + 1):
		if d % j == 0:
			return False
	return True
m = 100000007
t = int(input())
for i in range(t):
	(n, k1, k2) = map(int, input().split())
	(p1, p2, p3, p4) = map(int, input().split())
	p = int(math.sqrt(k1))
	if p * p < k1:
		p += 1
	c = 0
	ans = 0
	while p * p <= k2:
		c += 1
		if p != 1 and isprime(p):
			ans = (ans + p1) % m
		else:
			ans = (ans + p2) % m
		p += 1
	ans = (ans + p3 * (k2 - k1 + 1 - c) % m) % m
	print(ans)


for _ in range(int(input())):
	(n, k1, k2) = list(map(int, input().strip().split()))
	(p1, p2, p3, p4) = list(map(int, input().strip().split()))
	ans = [0] * (n + 1)
	for i in range(1, n + 1):
		j = i
		while j <= n:
			ans[j] += 1
			j += i
	cost = 0
	for i in range(k1, k2 + 1):
		if ans[i] == 3:
			cost += p1
		elif ans[i] % 2 == 1:
			cost += p2
		else:
			cost += p3
	print(cost)


import atexit
import io
import sys
import math
from collections import defaultdict, Counter
_INPUT_LINES = sys.stdin.read().splitlines()
input = iter(_INPUT_LINES).__next__
_OUTPUT_BUFFER = io.StringIO()
sys.stdout = _OUTPUT_BUFFER

@atexit.register
def write():
	sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())

def isprime(d):
	for j in range(2, int(math.sqrt(d)) + 1):
		if d % j == 0:
			return False
	return True
m = 100000007
t = int(input())
for i in range(t):
	(n, k1, k2) = list(map(int, input().split()))
	(p1, p2, p3, p4) = list(map(int, input().split()))
	p = int(math.sqrt(k1))
	if p * p < k1:
		p += 1
	c = 0
	ans = 0
	while p * p <= k2:
		c += 1
		if p != 1 and isprime(p):
			ans = (ans + p1) % m
		else:
			ans = (ans + p2) % m
		p += 1
	ans = (ans + p3 * (k2 - k1 + 1 - c) % m) % m
	print(ans)


maxx = 2 * 10 ** 4 + 1
has = [1] * maxx
mod = 100000007
for i in range(2, maxx):
	for j in range(i, maxx, i):
		has[j] += 1
odd = 0
even = 0
th = 0
l = []
for i in has:
	if i == 3:
		th += 1
	elif i % 2 == 0:
		even += 1
	else:
		odd += 1
	l.append([th, even, odd])
for t in range(1, int(input()) + 1):
	(n, k1, k2) = list(map(int, input().split()))
	(p1, p2, p3, p4) = list(map(int, input().split()))
	th = l[k2][0] - l[k1 - 1][0]
	even = l[k2][1] - l[k1 - 1][1]
	odd = l[k2][2] - l[k1 - 1][2]
	summ = th * p1 % mod + odd * p2 % mod + even * p3 % mod
	print(summ)


t = int(input())

class Container:

	def __init__(self):
		self.comp = [0, 0]
		self.state = -1

	def process(self):
		if self.state == -1 or self.state == 1:
			if self.comp == [1, 1]:
				self.state = 3
			else:
				self.state = 0
			self.comp[0] += 1
		elif self.state == 0 or self.state == 3:
			self.state = 1
			self.comp[1] += 1
for _ in range(t):
	(n, k1, k2) = map(int, input().split())
	(p1, p2, p3, p4) = map(int, input().split())
	containers = [Container() for _ in range(n)]
	sum = 0
	for i in range(1, n + 1):
		con = [x for x in range(1, n + 1) if x % i == 0]
		for ele in con:
			containers[ele - 1].process()
	for ele in containers[k1 - 1:k2]:
		if ele.state == 0:
			sum += p2
		elif ele.state == 3:
			sum += p1
		elif ele.state == 1:
			sum += p3
	print(sum)


primes = {}

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			primes[p] = 1
t = int(input())
SieveOfEratosthenes(10000)
factors = {1: 2, 2: 3}
for i in range(3, 6000):
	if i in primes:
		factors[i * i] = 1
	else:
		factors[i * i] = 2
for case in range(t):
	(n, k1, k2) = list([int(x) for x in input().split()])
	(p1, p2, p3, p4) = list([int(x) for x in input().split()])
	costs = [0, p1 % 100000007, p2 % 100000007, p3 % 100000007, p4 % 100000007]
	cost = 0
	numbers_to_remove = 0
	for number in factors:
		if number <= n and (number >= k1 and number <= k2 or (number <= k1 and number >= k2)):
			cost = cost + costs[factors[number]]
			numbers_to_remove += 1
	cost = (cost % 100000007 + (k2 - k1 + 1 - numbers_to_remove) * costs[3] % 100000007) % 100000007
	print(cost % 100000007)


t = int(input())
for _ in range(t):
	(n, k1, k2) = map(int, input().split())
	(p1, p2, p3, p4) = map(int, input().split())
	sum = 0
	cont = [[[0, 0], -1] for _ in range(n)]
	for i in range(1, n + 1):
		con = [x for x in range(1, n + 1) if x % i == 0]
		for ele in con:
			if cont[ele - 1][1] == -1:
				cont[ele - 1][1] = 0
				cont[ele - 1][0][0] += 1
			elif cont[ele - 1][1] == 0:
				cont[ele - 1][0][1] += 1
				cont[ele - 1][1] = 1
			elif cont[ele - 1][1] == 1:
				if cont[ele - 1][0] == [1, 1]:
					cont[ele - 1][1] = 3
				else:
					cont[ele - 1][1] = 0
				cont[ele - 1][0][0] += 1
			elif cont[ele - 1][1] == 3:
				cont[ele - 1][0][1] += 1
				cont[ele - 1][1] = 1
	for ele in cont[k1 - 1:k2]:
		if ele[1] == 0:
			sum += p2
		elif ele[1] == 2:
			sum += p4
		elif ele[1] == 3:
			sum += p1
		elif ele[1] == 1:
			sum += p3
	print(sum)


import math

def no_of_factors(n):
	count = 0
	for i in range(1, int(math.sqrt(n)) + 1):
		if n % i == 0:
			if n / i == i:
				count = count + 1
			else:
				count = count + 2
	return count
t = int(input())
for i in range(t):
	(n, k1, k2) = [int(x) for x in input().split()]
	(p1, p2, p3, p4) = [int(x) for x in input().split()]
	l = [-1 for x in range(k2 - k1 + 1)]
	for x in range(k1, k2 + 1):
		fact = no_of_factors(x)
		cont = x - k1
		if fact == 3:
			l[cont] = p1
		elif fact % 2 == 1:
			l[cont] = p2
		else:
			l[cont] = p3
	total = 0
	for x in l:
		total += x
	print(total)


primes = {}

def SieveOfEratosthenes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	for p in range(2, n + 1):
		if prime[p]:
			primes[p] = 1
t = int(input())
SieveOfEratosthenes(10000)
factors = {1: 2, 2: 3}
for i in range(3, 5000):
	if i in primes:
		factors[i * i] = 1
	else:
		factors[i * i] = 2
for case in range(t):
	(n, k1, k2) = list([int(x) for x in input().split()])
	(p1, p2, p3, p4) = list([int(x) for x in input().split()])
	costs = [0, p1, p2, p3, p4]
	cost = 0
	for i in range(k1, k2 + 1):
		if i in factors:
			cost += costs[factors[i]]
		else:
			cost += costs[3]
	print(cost)


import math
cn = [0, 0]
for _ in range(10000):
	cn.append(1)
for i in range(2, 10000):
	if cn[i] == 1:
		j = 2 * i
		while j < 10000:
			cn[j] = 0
			j += i
for i in range(1, 10000):
	cn[i] += cn[i - 1]
t = int(input())
for _ in range(t):
	(n, k1, k2) = (int(i) for i in input().split())
	(p1, p2, p3, p4) = (int(i) for i in input().split())
	s1 = math.floor(math.sqrt(k1 - 1))
	s2 = math.floor(math.sqrt(k2))
	pr = cn[s2] - cn[s1]
	ans = p1 * pr + p2 * (s2 - s1 - pr) + p3 * (k2 - k1 + 1 - s2 + s1)
	print(ans % 100000007)