The Indian bank issues coins in 4 denominations, ₹1, ₹2, ₹5 and ₹10. 

Given a limited supply of each of the above denominations, in how many ways can you sum them up to a total of ₹N?

Input Format 

The first line contains an integer T (number of testcases). 
Each testcase contains 2 lines. The first line contains integer N (sum to be achieved) 

A, B, C and D in the next line, each representing the number of ₹1, ₹2, ₹5 and ₹10 coins respectively. 

Output Format 

Output the number of ways in which we can achieve the sum N.   

Constraints 

1 <= T <= 150 

1 <= N <= 1000 

1 <= A <= 10000 

1 <= B,C,D <= 1000  

Sample Input  

2
15
2 3 1 1
12
2 2 1 1

Sample Output

2
2

Explanation 

In the first case we need to find the different ways to total to 15. 
We can use one ₹10 coin and one ₹5 coin  or one ₹10 coin two ₹2 coin and one ₹1 coin. Proceed similarly for the second case.

Difficulty: MEDIUM
Tags: Combinatorics

Starter code:

Solutions:
for i in range(int(input())):
	N = int(input())
	cs0 = tuple(map(int, input().split()))
	r = 0
	for i in range(min(cs0[3], N // 10) + 1):
		for j in range(min(cs0[2], (N - i * 10) // 5) + 1):
			cs = list(cs0)
			N1 = N - 10 * i - 5 * j
			if 2 * cs[1] + cs[0] < N1 or (N1 % 2 == 1 and cs[0] == 0):
				continue
			if N1 % 2 == 1:
				N1 -= 1
				cs[0] -= 1
			if cs[0] % 2 == 1:
				cs[0] -= 1
			min2 = max(N1 - cs[0], 0) // 2
			max2 = min(N1 // 2, cs[1])
			r += max2 - min2 + 1
	print(r)


up = 1000

def polymult(poly, rp, k, n):
	poly_ = [0] * (n + 1)
	poly_[0] = 0
	for i in range(0, min(rp * k, up) + 1, rp):
		for j in range(min(len(poly), n - i + 1)):
			poly_[i + j] += poly[j]
	return poly_
t = int(input())
for i in range(t):
	n = int(input())
	ar = [int(i) for i in input().split()]
	poly = [1] * (ar[0] + 1)
	poly = polymult(poly, 2, ar[1], n)
	poly = polymult(poly, 5, ar[2], n)
	poly = polymult(poly, 10, ar[3], n)
	print(poly[n])


T = int(input())
S = [1, 2, 5, 10]
for _ in range(T):
	N = int(input())
	L = list(map(int, input().strip().split()))
	A = [0] * (N + 1)
	B = list(A)
	for i in range(min(L[0], N) + 1):
		A[i] = 1
	for i in range(1, 4):
		for j in range(0, L[i] + 1):
			for k in range(N + 1 - j * S[i]):
				B[k + j * S[i]] += A[k]
		for j in range(0, N + 1):
			A[j] = B[j]
			B[j] = 0
	print(A[N])


W_ = {}

def nbWays(N, Ps):
	if len(Ps) == 1:
		if Ps[0][0] * Ps[0][1] < N:
			return 0
		if N % Ps[0][1] == 0:
			return 1
		return 0
	if (N, Ps) in W_:
		return W_[N, Ps]
	(w, m) = (0, min(N // Ps[0][1], Ps[0][0]))
	for n in range(0, m + 1):
		w += nbWays(N - n * Ps[0][1], Ps[1:])
	W_[N, Ps] = w
	return w
T = int(input())
for t in range(0, T):
	N = int(input())
	(A, B, C, D) = [int(x) for x in input().split(' ')]
	print(nbWays(N, ((D, 10), (C, 5), (B, 2), (A, 1))))


DENOMINATIONS = [1, 2, 5, 10]
cache = {}

def _solution(n, coins):
	for (d, dn) in coins.items():
		if dn is None:
			continue
		m = d * dn
		if m < n:
			new_coins = coins.copy()
			new_coins[d] = None
			return _solution(n, new_coins) - _solution(n - m - d, new_coins)
	return solution_full(n)

def solution_full(n, d_min=0):
	if n < 0:
		return 0
	if n == 0:
		return 1
	result = cache.get((n, d_min))
	if result is None:
		result = 0
		for d in DENOMINATIONS:
			if d >= d_min:
				result += solution_full(n - d, d)
		cache[n, d_min] = result
	return result

def solution(n, coins):
	return _solution(n, dict(zip(DENOMINATIONS, coins)))
t = int(input())
for _ in range(t):
	n = int(input())
	print(solution(n, [int(k) for k in input().split()]))


import sys
coins = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * coins[0] and n % coins[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * coins[k] <= n:
			total += count(memo, n - i * coins[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = [int(x) for x in sys.stdin.readline().split()]
	memo = {}
	print(count(memo, N, len(coins) - 1))


caseCnt = int(input())
for caseNr in range(caseCnt):
	ways = 0
	n = int(input())
	coins = [int(x) for x in input().split()]
	for i in range(min(coins[3] + 1, n // 10 + 1)):
		o = n - i * 10
		for j in range(min(coins[2] + 1, o // 5 + 1)):
			p = o - j * 5
			for k in range(min(coins[1] + 1, p // 2 + 1)):
				q = p - k * 2
				if coins[0] >= q:
					ways += 1
	print(ways)


import functools

def solve(ws, coins):

	def get_ones(ws):
		return 1 if ws <= coins[0] else 0

	@functools.lru_cache(maxsize=1024)
	def get_twos(ws):
		result = 0
		for i in range(coins[1] + 1):
			if i * 2 > ws:
				break
			result += get_ones(ws - i * 2)
		return result

	@functools.lru_cache(maxsize=1024)
	def get_fives(ws):
		result = 0
		for i in range(coins[2] + 1):
			if i * 5 > ws:
				break
			result += get_twos(ws - i * 5)
		return result

	@functools.lru_cache(maxsize=1024)
	def get_tens(ws):
		result = 0
		for i in range(coins[3] + 1):
			if i * 10 > ws:
				break
			result += get_fives(ws - i * 10)
		return result
	return get_tens(ws)
for _ in range(int(input())):
	print(solve(int(input()), [int(item) for item in input().split(' ')]))


def solve_me(n, n_coins):
	if n_coins[0] > n:
		n_coins[0] = n
	dp = [1 if i <= n_coins[0] else 0 for i in range(n + 1)]
	for (c, nc) in zip((2, 5, 10), n_coins[1:]):
		for i in range(n, 0, -1):
			for j in range(i - c, i - nc * c - 1, -c):
				if j < 0:
					break
				dp[i] += dp[j]
	return dp[n]
for _ in range(int(input())):
	n = int(input())
	n_coins = list(map(int, input().split(' ')))
	print(solve_me(n, n_coins))


import sys
COINS = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * COINS[0] and n % COINS[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * COINS[k] <= n:
			total += count(memo, n - i * COINS[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	memo = {}
	print(count(memo, N, len(COINS) - 1))


T = int(input())
for _ in range(T):
	N = int(input())
	coins = [int(x) for x in input().split()]
	possible_combs = 0
	for coins_10 in range(0, coins[3] + 1):
		if coins_10 * 10 > N:
			break
		for coins_5 in range(0, coins[2] + 1):
			current_sum = coins_10 * 10 + coins_5 * 5
			if current_sum > N:
				break
			coins_2_ceil = min((N - current_sum) // 2, coins[1])
			coins_2_bottom = max((N - current_sum - coins[0] + 1) // 2, 0)
			if coins_2_bottom > coins_2_ceil:
				continue
			possible_combs += coins_2_ceil - coins_2_bottom + 1
	print(possible_combs)


import sys
COINS = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * COINS[0] and n % COINS[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * COINS[k] <= n:
			total += count(memo, n - i * COINS[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	memo = {}
	print(count(memo, N, len(COINS) - 1))


for T in range(int(input())):
	(N, ans) = (int(input()), 0)
	(A, B, C, D) = map(int, input().split())
	for i in range(min(N // 10, D) + 1):
		for j in range(min((N - 10 * i) // 5, C) + 1):
			M = N - 10 * i - 5 * j
			ans += max(0, min(M // 2, B) - (max(0, M - A) + 1) // 2 + 1)
	print(ans)


import functools

@functools.lru_cache(102400)
def mk_change(amounts, target):
	amounts = list(amounts)
	if len(amounts) == 0:
		if target == 0:
			return 1
		else:
			return 0
	head = amounts[0]
	tail = amounts[1:]
	max_tail = sum((a * b for (a, b) in tail))
	res = 0
	for take in range(head[1] + 1):
		val = take * head[0]
		if val > target:
			break
		if target - val <= max_tail:
			res += mk_change(tuple(tail), target - val)
	return res
T = int(input())
for t in range(T):
	target = int(input())
	amounts = [int(v) for v in input().strip().split(' ')]
	values = [1, 2, 5, 10]
	print(mk_change(tuple(zip(values[::-1], amounts[::-1])), target))


numTests = int(input())
for test in range(numTests):
	total = int(input())
	(A, B, C, D) = [int(n) for n in input().split()]
	count = 0
	maxAvailable = [A, A + 2 * B, A + 2 * B + 5 * C]
	for num10 in range(min(D, total // 10) + 1):
		left10 = total - 10 * num10
		if left10 > maxAvailable[2]:
			continue
		for num5 in range(min(C, left10 // 5) + 1):
			left5 = total - 10 * num10 - 5 * num5
			if left5 > maxAvailable[1]:
				continue
			for num2 in range(min(B, left5 // 2) + 1):
				if left5 - 2 * num2 <= A:
					count += 1
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	(a, b, c, d) = map(int, input().split())
	left = a + 2 * b + 5 * c + 10 * d
	sd = [10 * i for i in range(min(d, n // 10) + 1)]
	sc = [s + 5 * i for s in sd for i in range(min(c, (n - s) // 5) + 1)]
	sb = [s + 2 * i for s in sc for i in range(min(b, (n - s) // 2) + 1)]
	print(len([s for s in sb if n - s <= a]))


import sys
COINS = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * COINS[0] and n % COINS[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * COINS[k] <= n:
			total += count(memo, n - i * COINS[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	memo = {}
	print(count(memo, N, len(COINS) - 1))


COINS = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * COINS[0] and n % COINS[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * COINS[k] <= n:
			total += count(memo, n - i * COINS[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(x) for x in input().split()]
	memo = {}
	print(count(memo, N, len(COINS) - 1))


import sys
COINS = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * COINS[0] and n % COINS[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * COINS[k] <= n:
			total += count(memo, n - i * COINS[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	memo = {}
	print(count(memo, N, len(COINS) - 1))


T = int(input())
for _ in range(T):
	N = int(input())
	(total_ones, total_twos, total_fives, total_tens) = [int(i) for i in input().split()]
	count = 0
	for tens in range(1 + min(total_tens, N // 10)):
		for fives in range(1 + min(total_fives, (N - 10 * tens) // 5)):
			remaining = N - 10 * tens - 5 * fives
			if remaining > total_ones + 2 * total_twos:
				continue
			min_twos = max(0, (1 + remaining - total_ones) // 2)
			max_twos = min(total_twos, remaining // 2)
			count += 1 + max_twos - min_twos
	print(count)


def get_array(size):
	ret = []
	for _ in range(size):
		ret.append(0)
	return ret

def get_pattern(a, b, c, d, n):
	value = [1, 2, 5, 10]
	l = [a, b, c, d]
	dp = []
	for i in range(4):
		dp.append(get_array(n + 1))
	for j in range(min(a + 1, n + 1)):
		dp[0][j] = 1
	for i in range(1, 4):
		for j in range(n + 1):
			sum = 0
			for k in range(l[i] + 1):
				if j - value[i] * k >= 0:
					sum += dp[i - 1][j - value[i] * k]
			dp[i][j] = sum
	print(dp[3][n])
t = int(input())
for _ in range(t):
	n = int(input())
	(a, b, c, d) = [int(v) for v in input().split()]
	get_pattern(a, b, c, d, n)


import sys
COINS = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * COINS[0] and n % COINS[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * COINS[k] <= n:
			total += count(memo, n - i * COINS[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	memo = {}
	print(count(memo, N, len(COINS) - 1))


import sys
COINS = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * COINS[0] and n % COINS[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * COINS[k] <= n:
			total += count(memo, n - i * COINS[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	memo = {}
	print(count(memo, N, len(COINS) - 1))


import sys
COINS = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * COINS[0] and n % COINS[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * COINS[k] <= n:
			total += count(memo, n - i * COINS[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	memo = {}
	print(count(memo, N, len(COINS) - 1))


import sys
COINS = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * COINS[0] and n % COINS[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * COINS[k] <= n:
			total += count(memo, n - i * COINS[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(sys.stdin.readline())
for _ in range(T):
	N = int(sys.stdin.readline())
	A = list(map(int, sys.stdin.readline().split()))
	memo = {}
	print(count(memo, N, len(COINS) - 1))


from collections import defaultdict
testcases = int(input().strip())
for case in range(testcases):
	goal = int(input().strip())
	mmax = [int(x) for x in input().strip().split()]
	vval = [1, 2, 5, 10]
	totals = defaultdict(int)
	totals[0] = 1
	for (imax, ival) in zip(mmax, vval):
		new_totals = totals.copy()
		for i in range(ival, min(imax * ival, goal) + 1, ival):
			for t in totals:
				if i + t <= goal:
					new_totals[i + t] += totals[t]
		totals = new_totals
	print(totals[goal])


import math
T = int(input())
for tmp in range(T):
	cnt_tot = 0
	N = int(input())
	[A, B, C, D] = list(map(int, input().strip().split(' ')))
	for cntD in range(D + 1):
		sumD = cntD * 10
		if sumD > N:
			break
		for cntC in range(C + 1):
			sumC = sumD + cntC * 5
			if sumC > N:
				break
			minB = math.ceil((N - sumC - A) / 2.0)
			maxB = math.floor((N - sumC) / 2.0)
			if B < minB or maxB < minB:
				continue
			cnt_tot += min([B, maxB]) - max([minB, 0]) + 1
	print(cnt_tot)


coins = [1, 2, 5, 10]

def count(used, curr_sum, start_level, Coin_No):
	if (curr_sum, start_level) in used:
		return used[curr_sum, start_level]
	elif start_level == 0:
		return int(curr_sum <= Coin_No[0] * coins[0] and curr_sum % coins[0] == 0)
	else:
		(test_count, total_comb) = (0, 0)
		while test_count <= Coin_No[start_level] and test_count * coins[start_level] <= curr_sum:
			total_comb += count(used, curr_sum - test_count * coins[start_level], start_level - 1, Coin_No)
			test_count += 1
		used[curr_sum, start_level] = total_comb
		return total_comb
for _ in range(int(input())):
	N = int(input())
	Coin_No = [int(x) for x in input().split()]
	used = {}
	print(count(used, N, len(coins) - 1, Coin_No))


t = int(input())
for _ in range(t):
	n = int(input())
	(a, b, c, d) = map(int, input().split())
	r = 0
	s = {}
	for i in range(min(a, n) + 1):
		for j in range(min(b, n // 2) + 1):
			x = n - (i + 2 * j)
			if x % 5 == 0:
				y = x // 5
				if y not in s:
					s[y] = 0
				s[y] += 1
	for i in range(min(c, n // 5) + 1):
		for j in range(min(d, n // 10) + 1):
			x = i + 2 * j
			if x in s:
				r += s[x]
	print(r)


for _ in range(int(input())):
	total = int(input())
	(one, two, five, ten) = map(int, input().strip().split())
	(one_two, five_ten) = ({}, {})
	for i in range(one + 1):
		if i > total:
			break
		for j in range(0, two * 2 + 1, 2):
			if i + j not in one_two:
				one_two[i + j] = 0
			one_two[i + j] += 1
			if j > total:
				break
	for i in range(0, five * 5 + 1, 5):
		if i > total:
			break
		for j in range(0, ten * 10 + 1, 10):
			if i + j not in five_ten:
				five_ten[i + j] = 0
			five_ten[i + j] += 1
			if j > total:
				break
	ans = 0
	for (x, x_) in five_ten.items():
		y = total - x
		if y in one_two:
			ans += one_two[y] * x_
	print(ans)


class Ways(object):

	def __init__(self, coinLimits):
		self.coinLimits = coinLimits
		self._coins = (1, 2, 5, 10)

	def getWays(self, I, N):
		ways = [None] * 4
		ways[0] = [1] + [1] * min(N, self.coinLimits[0])
		while len(ways[0]) < N + 1:
			ways[0].append(0)
		for (i, coin_value) in enumerate(self._coins):
			if i == 0:
				continue
			ways[i] = list(ways[i - 1])
			for n_coins in range(1, self.coinLimits[i] + 1):
				value_added = self._coins[i] * n_coins
				if value_added > N:
					break
				for j in range(0, N - value_added + 1):
					ways[i][j + value_added] += ways[i - 1][j]
		return ways[I][N]
for _ in range(int(input())):
	N = int(input())
	coinLimits = tuple(map(int, input().split()))
	coins = (1, 2, 5, 10)
	print(Ways(coinLimits).getWays(3, N))


from sys import stdin
from itertools import accumulate as acc, count, combinations_with_replacement as cmbrep, takewhile as tkw, repeat as rp, dropwhile as dpw
from functools import reduce
from random import randint
from collections import Counter
from math import sqrt, log
from fractions import gcd
from heapq import merge
from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)
filou = None

def do12(N, A, B, C=0, D=0):
	if 2 * B + A < N:
		return 0
	if N & 1:
		(A, N) = (A - 1, N - 1)
	if A & 1:
		A -= 1
	if N > A:
		B -= (N - A) // 2
		N = A
	return min(B + 1, 1 + N // 2)

def do(N, A, B, C, D):
	(minH, maxH) = (max(0, N - (2 * B + A)) // 5, min(N, 5 * (2 * D + C)) // 5)
	if trace & 1:
		print(minH, maxH)
	return sum((do12(N - 5 * H, A, B) * do12(H, C, D) for H in range(minH, maxH + 1)))
if home:
	from mesures import ch, prof
trace = 0
prof = 0
tst = 0
if filou:
	print('lecture de', filou)
	rd = open(filou, 'r')
else:
	rd = stdin
for _ in range(int(rd.readline().strip())):
	N = int(rd.readline().strip())
	(A, B, C, D) = map(int, rd.readline().strip().split())
	print(do(N, A, B, C, D))


def f(A, B, C, D, N):
	if B + C + D == 0:
		if A < N:
			return 0
		return 1
	if C + D == 0:
		s = 0
		for i in range(min(N // 2, B) + 1):
			s += f(A, 0, 0, 0, N - 2 * i)
		return s
	if D == 0:
		s = 0
		for i in range(min(N // 5, C) + 1):
			s += f(A, B, 0, 0, N - 5 * i)
		return s
	s = 0
	for i in range(min(N // 10, D) + 1):
		s += f(A, B, C, 0, N - 10 * i)
	return s
num_tests = int(input().strip())
for i in range(num_tests):
	N = int(input().strip())
	(A, B, C, D) = [int(x) for x in input().strip().split()]
	print(f(A, B, C, D, N))


cache = {}

def solve(coins, last, a, b, c, d, n):
	if last < 0:
		return 0
	if n == 0:
		return 1
	if n < 0:
		return 0
	t = (last, a, b, c, d, n)
	if t in cache:
		return cache[t]
	ret = 0
	if (a, b, c, d)[last] > 0 and n - coins[last] >= 0:
		if last == 0:
			ret += solve(coins, last, a - (1 if a < n else 0), b, c, d, n - coins[last])
		elif last == 1:
			ret += solve(coins, last, a, b - 1, c, d, n - coins[last])
		elif last == 2:
			ret += solve(coins, last, a, b, c - 1, d, n - coins[last])
		elif last == 3:
			ret += solve(coins, last, a, b, c, d - 1, n - coins[last])
	if last == 3:
		ret += solve(coins, last - 1, a, b, c, 0, n)
	elif last == 2:
		ret += solve(coins, last - 1, a, b, 0, 0, n)
	elif last == 1:
		ret += solve(coins, last - 1, a, 0, 0, 0, n)
	elif last == 0:
		ret += solve(coins, last - 1, 0, 0, 0, 0, n)
	cache[t] = ret
	return ret
t = int(input())
coins = [1, 2, 5, 10]
for i in range(t):
	n = int(input())
	quantities = list(map(int, input().strip().split(' ')))
	print(solve(coins, 3, quantities[0], quantities[1], quantities[2], quantities[3], n))


from math import floor

def A(a, b, c, d, N):
	amount = {1: a, 2: b, 5: c, 10: d}
	L = [0 for _ in range(N + 1)]
	L[0] = 1
	for coin in {1, 2, 5, 10}:
		temp = [0 for x in range(N + 1)]
		for x in range(1, min(floor(N / coin), amount[coin]) + 1):
			for i in range(N - coin * x + 1):
				temp[i + coin * x] += L[i]
		for i in range(N + 1):
			L[i] += temp[i]
	return L[N]
T = int(input())
for _ in range(T):
	N = int(input())
	(a, b, c, d) = (int(x) for x in input().split())
	print(A(a, b, c, d, N))


import time
import math

def n_ways(total, n1, n2, n5, n10, cached_results=dict()):
	if total == 0:
		return 1
	key = ','.join((str(i) for i in (total, n1, n2, n5, n10)))
	cached_result = cached_results.get(key)
	if cached_result:
		return cached_result
	n_ways1 = 0
	n_ways2 = 0
	n_ways5 = 0
	n_ways10 = 0
	if total >= 1:
		n_ways1 = n1 >= total
	if total >= 2:
		min_count = 1
		if n2 >= min_count:
			n_ways2 = n_ways(total - min_count * 2, n1, n2 - min_count, 0, 0, cached_results)
	if total >= 5:
		min_count = 1
		if n5 >= min_count:
			n_ways5 = n_ways(total - min_count * 5, n1, n2, n5 - min_count, 0, cached_results)
	if total >= 10:
		min_count = 1
		if n10 >= min_count:
			n_ways10 = n_ways(total - min_count * 10, n1, n2, n5, n10 - min_count, cached_results)
	result = n_ways1 + n_ways2 + n_ways5 + n_ways10
	cached_results[key] = result
	return result
n_testcases = int(input().strip())
for _ in range(n_testcases):
	total = int(input().strip())
	(n1, n2, n5, n10) = [int(i) for i in input().strip().split()]
	print(n_ways(total, n1, n2, n5, n10))


def Combos(N, A, B, C, D):
	total = 0
	if A > 0:
		total += Combos(N, 0, B, C, D)
		while A > 0 and N >= 10:
			A -= 1
			N -= 10
			total += Combos(N, 0, B, C, D)
	elif B > 0:
		total += Combos(N, 0, 0, C, D)
		while B > 0 and N >= 5:
			B -= 1
			N -= 5
			total += Combos(N, 0, 0, C, D)
	elif C > 0:
		total += Combos(N, 0, 0, 0, D)
		while C > 0 and N >= 2:
			C -= 1
			N -= 2
			total += Combos(N, 0, 0, 0, D)
	elif D >= N:
		return 1
	return total

def DoTest():
	N = int(input())
	(D, C, B, A) = input().split()
	(A, B, C, D) = (int(A), int(B), int(C), int(D))
	print(Combos(N, A, B, C, D))
Tests = int(input())
for i in range(0, Tests):
	DoTest()


import sys
from time import time
cache = {}

def count(aa, n):
	if n == 0:
		return 1
	if not aa:
		return 0
	t = (tuple(aa), n)
	if t in cache:
		return cache[t]
	sm = 0
	for i in range(1):
		(denomination, coins) = aa[i]
		u = n
		for _ in range(coins + 1):
			if u < 0:
				break
			sm += count(aa[:i] + aa[i + 1:], u)
			u -= denomination
	cache[t] = sm
	return cache[t]
tm = time()
t = int(input())
for _ in range(t):
	n = int(input())
	cc = map(int, input().split())
	dd = (1, 2, 5, 10)
	aa = tuple(zip(dd, cc))
	print(count(aa, n))
print('time elapsed: %s' % (time() - tm), file=sys.stderr)


def check(a, b, c, d):
	return a + 2 * b + 5 * c + 10 * d

def f(a, b, c, d):
	if (a, b, c, d) in dn:
		return 0
	if check(a, b, c, d) == N:
		dn[a, b, c, d] = 1
		return 1
	dn[a, b, c, d] = 1
	res = 0
	if a < A and check(a + 1, b, c, d) <= N:
		res += f(a + 1, b, c, d)
	if b < B and check(a, b + 1, c, d) <= N:
		res += f(a, b + 1, c, d)
	if c < C and check(a, b, c + 1, d) <= N:
		res += f(a, b, c + 1, d)
	if d < D and check(a, b, c, d + 1) <= N:
		res += f(a, b, c, d + 1)
	return res
for _ in range(int(input())):
	N = int(input())
	(a, b, c, d) = list(map(int, input().split()))
	res = 0
	dn1 = {}
	dn2 = {}
	for i in range(a + 1):
		if i > N:
			break
		for j in range(b + 1):
			if i + 2 * j > N:
				break
			if i + 2 * j not in dn1:
				dn1[i + 2 * j] = 1
			else:
				dn1[i + 2 * j] += 1
	for i in range(c + 1):
		if i * 5 > N:
			break
		for j in range(d + 1):
			if 5 * i + 10 * j > N:
				break
			if 5 * i + 10 * j not in dn2:
				dn2[5 * i + 10 * j] = 1
			else:
				dn2[5 * i + 10 * j] += 1
	for key2 in dn2.keys():
		if N - key2 in dn1:
			res += dn2[key2] * dn1[N - key2]
	print(res)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	(a, b, c, d) = list(map(int, input().split()))
	count = 0
	for i in range(n // 5 + 1):
		for d1 in range(min(d + 1, i // 2 + 1)):
			k = i - 2 * d1
			if k <= c:
				y = n - 5 * i
				for b1 in range(min(b + 1, y // 2 + 1)):
					k = y - 2 * b1
					if k <= a:
						count += 1
	print(count)


def makeIndex(change, ndenoms):
	return 4 * change + ndenoms

def countWays(N, ndenoms, denoms, quants, memos):
	denom = denoms[ndenoms - 1]
	if N == 0:
		return (1, memos)
	elif ndenoms == 1:
		possible = N % denom == 0 and N // denom <= quants[ndenoms - 1]
		return (possible, memos)
	elif makeIndex(N, ndenoms - 1) in memos:
		return (memos[makeIndex(N, ndenoms - 1)], memos)
	else:
		count = 0
		money = N
		for i in range(quants[ndenoms - 1] + 1):
			(subCount, memos) = countWays(money, ndenoms - 1, denoms, quants, memos)
			count += subCount
			money -= denom
			if money < 0:
				break
		memos[makeIndex(N, ndenoms - 1)] = count
		return (count, memos)
line = input()
ctests = int(line)
for itest in range(ctests):
	line = input()
	N = int(line)
	line = input()
	tokens = line.split()
	quants = [int(tokens[0]), int(tokens[1]), int(tokens[2]), int(tokens[3])]
	denoms = [1, 2, 5, 10]
	(count, memos) = countWays(N, len(denoms), denoms, quants, {})
	print(count)


def helper(denomination, number, beforeList):
	sumList = [0] * len(beforeList)
	for i in range(1, number + 1):
		startIndex = i * denomination
		for j in range(len(beforeList) - startIndex):
			sumList[j + startIndex] += beforeList[j]
	for i in range(len(beforeList)):
		beforeList[i] += sumList[i]
for _ in range(int(input())):
	n = int(input())
	(one, two, five, ten) = [int(x) for x in input().split()]
	initList = [0] * (n + 1)
	initList[0] = 1
	helper(1, one, initList)
	helper(2, two, initList)
	helper(5, five, initList)
	helper(10, ten, initList)
	print(initList[-1])


import math
T = int(input())
prev_answers = {}
for _ in range(T):
	N = int(input())
	inputs = (A, B, C, D) = map(int, input().split())
	if inputs in prev_answers:
		print(prev_answers[input])
		continue
	num_ways = 0
	for d in range(D + 1):
		new_total_1 = N - d * 10
		if new_total_1 < 0:
			break
		for c in range(C + 1):
			new_total_2 = new_total_1 - c * 5
			if new_total_2 < 0:
				break
			if new_total_2 % 2 == 1 and A == 0:
				break
			min_twos = max(math.ceil((new_total_2 - A) / 2), 0)
			max_twos = math.floor(new_total_2 / 2)
			for b in range(min_twos, max_twos + 1):
				if b > B:
					break
				num_ways += 1
	prev_answers[inputs] = num_ways
	print(num_ways)


import math
T = int(input())

def count_twos(amount, twos, ones):
	start = max(0, math.ceil((amount - ones) / 2))
	end = min(twos, amount // 2)
	if start <= end:
		return end - start + 1
	else:
		return 0

def count_fives(amount, fives, twos, ones):
	start = max(0, math.ceil((amount - 2 * twos - ones) / 5))
	end = min(fives, amount // 5)
	output = 0
	if start <= end:
		for ii in range(start, end + 1):
			output += count_twos(amount - 5 * ii, twos, ones)
	return output

def count_tens(amount, tens, fives, twos, ones):
	start = max(0, math.ceil((amount - 5 * fives - 2 * twos - ones) / 10))
	end = min(tens, amount // 10)
	output = 0
	if start <= end:
		for ii in range(start, end + 1):
			output += count_fives(amount - 10 * ii, fives, twos, ones)
	return output
for _ in range(T):
	amount = int(input())
	(a, b, c, d) = [int(ii) for ii in input().split()]
	print(count_tens(amount, d, c, b, a))


class Solution(object):

	def __init__(self):
		self.coinage = [1, 2, 5, 10]
		self.count = {}
		self.A = None

	def solve(self, cipher):
		(target, self.A) = cipher
		return self.get_count(target, 3)

	def get_count(self, n, k):
		if (n, k) not in self.count:
			if k == 0:
				if n % self.coinage[k] == 0 and self.coinage[k] * self.A[k] >= n:
					self.count[n, k] = 1
				else:
					self.count[n, k] = 0
			else:
				i = 0
				cnt = 0
				while i <= self.A[k] and i * self.coinage[k] <= n:
					cnt += self.get_count(n - i * self.coinage[k], k - 1)
					i += 1
				self.count[n, k] = cnt
		return self.count[n, k]
t = int(input())
for _ in range(t):
	target = int(input())
	lst = [int(i) for i in input().split()]
	cipher = (target, lst)
	s = '%s\n' % Solution().solve(cipher)
	print('{}'.format(s), end='')


W_ = {}

def nbWays(N, Ps):
	if len(Ps) == 1:
		if Ps[0][0] * Ps[0][1] < N:
			return 0
		if N % Ps[0][1] == 0:
			return 1
		return 0
	if (N, Ps) in W_:
		return W_[N, Ps]
	(w, m) = (0, min(N // Ps[0][1], Ps[0][0]))
	for n in range(0, m + 1):
		w += nbWays(N - n * Ps[0][1], Ps[1:])
	W_[N, Ps] = w
	return w
T = int(input())
for t in range(0, T):
	N = int(input())
	(A, B, C, D) = [int(x) for x in input().split(' ')]
	print(nbWays(N, ((D, 10), (C, 5), (B, 2), (A, 1))))


from math import floor
T = int(input())
for _ in range(T):
	N = int(input())
	(A, B, C, D) = map(int, input().split())
	x = floor(N / 5)
	(x_1, x_2, x_3, x_4) = (0, 0, 0, 0)
	total = 0
	for i in range(x + 1):
		y = N - i * 5
		Tx = 0
		Ty = 0
		(x_1, x_2, x_3, x_4) = (0, 0, 0, 0)
		while x_4 <= D:
			x_3 = i - 2 * x_4
			if x_3 <= C and x_3 >= 0:
				Tx += 1
			x_4 += 1
		while x_2 <= B:
			x_1 = y - 2 * x_2
			if x_1 <= A and x_1 >= 0:
				Ty += 1
			x_2 += 1
		total += Tx * Ty
	print(total)


def solve(C, n, A):
	if (len(C), n) in D:
		return D[len(C), n]
	if n == 0:
		return 1
	if len(C) == 1:
		if (n % C[0] == 0) & (n // C[0] <= A[0]):
			return 1
		return 0
	s = 0
	for i in range(A[0] + 1):
		if n < C[0] * i:
			break
		if n == C[0] * i:
			s += 1
			continue
		temp = solve(C[1:], n - i * C[0], A[1:])
		D[len(C) - 1, n - i * C[0]] = temp
		s += temp
	return s
T = int(input())
C = [1, 2, 5, 10]
for t0 in range(T):
	N = int(input())
	A = [int(a) for a in input().split()]
	D = {}
	print(solve(C, N, A))


def get_count_for_two(total_sum, max_a, max_b):
	if max_a + 2 * max_b < total_sum:
		return 0
	max_b_b = total_sum // 2
	if max_b_b > max_b:
		max_b_b = max_b
	min_v = total_sum - max_a
	res = 0
	if min_v <= 0:
		res = max_b_b + 1
	elif min_v % 2 == 0:
		res = 1 + max_b_b - min_v // 2
	else:
		res = 1 + max_b_b - (min_v + 1) // 2
	return res

def get_count_for_three(total_sum, max_a, max_b, max_c):
	if max_a + 2 * max_b + 5 * max_c < total_sum:
		return 0
	res = 0
	for index in range(max_c + 1):
		temp_sum = total_sum - index * 5
		if temp_sum > 0:
			temp_val = get_count_for_two(temp_sum, max_a, max_b)
			res += temp_val
		elif temp_sum == 0:
			res += 1
		elif temp_sum < 0:
			break
	return res

def get_count_for_four(total_sum, max_a, max_b, max_c, max_d):
	if max_a + 2 * max_b + 5 * max_c + 10 * max_d < total_sum:
		return 0
	res = 0
	for index in range(max_d + 1):
		temp_sum = total_sum - index * 10
		if temp_sum > 0:
			temp_val = get_count_for_three(temp_sum, max_a, max_b, max_c)
			res += temp_val
		elif temp_sum == 0:
			res += 1
		elif temp_sum < 0:
			break
	return res
T = int(input().strip())
for _ in range(T):
	N = int(input().strip())
	arr = [int(arr_temp) for arr_temp in input().strip().split(' ')]
	res = get_count_for_four(N, arr[0], arr[1], arr[2], arr[3])
	print(res)


n = int(input())
for i in range(n):
	tot = int(input())
	way = 0
	(a, b, c, d) = input().strip().split(' ')
	(a, b, c, d) = [int(a), int(b), int(c), int(d)]
	d_num = int(tot / 10 + 1)
	for i in range(d_num):
		rem = tot - 10 * i
		if i <= d:
			c_num = int(rem / 5 + 1)
			for j in range(c_num):
				rem1 = rem - 5 * j
				if j <= c:
					b_num = int(rem1 / 2 + 1)
					for k in range(b_num):
						if k <= b:
							if rem1 - 2 * k <= a:
								way += 1
	print(way)


import sys
n = int(input())
cv = {0: 1, 1: 2, 2: 5, 3: 10}

def pack(coin, max, coins):
	if coin == 0:
		if coins[0] >= max:
			return 1
		else:
			return 0
	else:
		sum = 0
		newCoin = coin - 1
		for i in range(0, divmod(max, cv[coin])[0] + 1):
			if coins[coin] >= i:
				newMax = max - cv[coin] * i
				sum = sum + pack(newCoin, newMax, coins)
		return sum
for i in range(n):
	target = int(input())
	coins = [int(i) for i in input().split(' ')]
	print(pack(3, target, coins))


class solver:

	def __init__(self, C):
		self._memo = {}
		self._C = C

	def solve(self, N, i0=0):
		if N == 0:
			return 1
		k = (N, i0)
		try:
			return self._memo[k]
		except:
			pass
		total = 0
		for i in range(i0, len(self._C)):
			(denom, coins) = self._C[i]
			N0 = N
			while coins > 0 and N0 - denom >= 0:
				N0 -= denom
				coins -= 1
				total += self.solve(N0, i + 1)
		self._memo[k] = total
		return total
for _ in range(int(input())):
	N = int(input())
	C = list(zip([1, 2, 5, 10], [int(tmp) for tmp in input().split(' ')]))
	S = solver(C)
	print(S.solve(N))


__LOG = False

def log(*args, **kwargs):
	if __LOG:
		print(*args, **kwargs)
denoms = [1, 2, 5, 10]
total_limit = 1000

def coinage(coins):
	coinage_table = [[None] * len(denoms) for t in range(total_limit + 1)]

	def _coinage(total, curr_d=len(denoms) - 1):
		if total < 0 or curr_d < 0:
			return 0
		res = coinage_table[total][curr_d]
		if res is None:
			res = __coinage(total, curr_d)
			coinage_table[total][curr_d] = res
		return res

	def __coinage(total, curr_d):
		if total == 0:
			return 1
		if curr_d == 0:
			if total / denoms[0] > coins[0] or total % denoms[0] != 0:
				return 0
			else:
				return 1
		n_combos = 0
		denom = denoms[curr_d]
		coin_count = 0
		while total >= 0 and coin_count <= coins[curr_d]:
			n_combos += _coinage(total, curr_d - 1)
			total -= denom
			coin_count += 1
		return n_combos
	return _coinage
n_cases = int(input())
for case in range(n_cases):
	total = int(input())
	coins = [int(x) for x in input().split()]
	assert len(coins) == len(denoms)
	n_combos = coinage(coins)(total)
	print(n_combos)


import sys
from collections import Counter

def solve(coin_counts, N):
	(A, B, C, D) = coin_counts
	left_counts = Counter()
	for a in range(min(A + 1, N + 1)):
		for b in range(min(B + 1, N // 2 + 1)):
			left_counts[a + 2 * b] += 1
	right_counts = Counter()
	for c in range(min(C + 1, N // 5 + 1)):
		for d in range(min(D + 1, N // 10 + 1)):
			right_counts[N - 5 * c - 10 * d] += 1
	total_count = 0
	for middle_count in left_counts:
		if middle_count in right_counts:
			total_count += left_counts[middle_count] * right_counts[middle_count]
	return total_count

def main(inp=sys.stdin):
	T = int(inp.readline().strip())
	for testcase in range(T):
		N = int(inp.readline().strip())
		coin_count = [int(x) for x in inp.readline().strip().split()]
		print(solve(coin_count, N))
main()


nt = int(input())
for _ in range(nt):
	nn = int(input())
	(n1, n2, n5, n10) = list(map(int, input().split()))
	ncomb = 0
	max10 = min(nn // 10, n10)
	for k1 in range(max10 + 1):
		ncurr = nn - 10 * k1
		max5 = min(ncurr // 5, n5)
		for k2 in range(max5 + 1):
			ncurr = nn - 10 * k1 - 5 * k2
			max2 = min(ncurr // 2, n2)
			for k3 in range(max2 + 1):
				if ncurr - 2 * k3 <= n1:
					ncomb = ncomb + 1
	print(ncomb)


T = int(input())

def find12(N, A, B):
	count = 0
	for n in range(N + 1):
		if (N - n) % 2 == 0:
			if n <= A and (N - n) / 2 <= B:
				count += 1
	return count
for t in range(T):
	N = int(input())
	(A, B, C, D) = map(int, input().strip().split(' '))
	count = 0
	for X in range(N + 1):
		if (N - X) % 5 == 0:
			count += find12(X, A, B) * find12((N - X) // 5, C, D)
	print(count)


values = [1, 2, 5, 10]
for _ in range(int(input())):
	n = int(input())
	dp = [0] * (n + 1)
	dp[0] = 1
	coins = [int(x) for x in input().split()]
	for (c, v) in zip(coins, values):
		newDp = [i for i in dp]
		for i in range(1, c + 1):
			for j in range(n + 1 - i * v):
				if j + i * v <= n:
					newDp[j + i * v] += dp[j]
		dp = newDp
	print(dp[n])


import sys
COINS = [1, 2, 5, 10]

def count(memo, n, k):
	if (n, k) in memo:
		return memo[n, k]
	elif k == 0:
		return int(n <= A[0] * COINS[0] and n % COINS[0] == 0)
	else:
		(i, total) = (0, 0)
		while i <= A[k] and i * COINS[k] <= n:
			total += count(memo, n - i * COINS[k], k - 1)
			i += 1
		memo[n, k] = total
		return total
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	memo = {}
	print(count(memo, N, len(COINS) - 1))


T = int(input())
for _ in range(T):
	cnt = 0
	N = int(input())
	(A, B, C, D) = list(map(int, input().strip().split()))
	for d in range(min(N // 10, D) + 1):
		N1 = N - 10 * d
		for c in range(min(N1 // 5, C) + 1):
			N2 = N1 - 5 * c
			for b in range(min(N2 // 2, B) + 1):
				N3 = N2 - 2 * b
				if N3 <= A:
					cnt += 1
	print(cnt)


def getWays(n, c, amount):
	p = [1]
	q = [0] * n
	l = p + q
	idxdic = {1: 0, 2: 1, 5: 2, 10: 3}
	for coin in c:
		temp = list(l)
		if coin < n + 2:
			for i in range(0, n + 1):
				if temp[i] != 0:
					count = 0
					for j in range(i + coin, n + 1, coin):
						if count < amount[idxdic[coin]]:
							l[j] += temp[i]
							count += 1
						else:
							break
	return l[n]
c = [1, 2, 5, 10]
t = int(input().strip())
for test in range(t):
	n = int(input().strip())
	amount = list(map(int, input().strip().split(' ')))
	x = getWays(n, c, amount)
	print(x)


def getWays(n, c, a):
	l = [0] * (n + 1)
	l[0] = 1
	idxDic = {1: 0, 2: 1, 5: 2, 10: 3}
	for coin in c:
		temp = list(l)
		if coin < n + 2:
			for i in range(n + 1):
				if temp[i] != 0:
					count = 0
					for j in range(i + coin, n + 1, coin):
						if count < a[idxDic[coin]]:
							l[j] += temp[i]
							count += 1
						else:
							break
	return l[n]
T = int(input().strip())
for i in range(T):
	N = int(input().strip())
	amount = [int(j) for j in input().strip().split(' ')]
	print(getWays(N, [1, 2, 5, 10], amount))


T = int(input())
value = [1, 2, 5, 10]
for t in range(T):
	N = int(input())
	coins = [int(x) for x in input().split()]
	ways = [0] * (N + 1)
	ways[0] = 1
	for i in range(len(value)):
		new = list(ways)
		d = coins[i] * value[i]
		for j in range(min(value[i], N)):
			t = ways[j]
			for k in range(j + value[i], N + 1, value[i]):
				new[k] += t
				t += ways[k]
				if k >= d:
					t -= ways[k - d]
		ways = new
	print(ways[N])


def CountWays(n, a, b, c, d):
	m = 0
	for k in range(n // 5 + 1):
		imin = max(0, (k - c + 1) // 2)
		imax = min(k // 2, d)
		m5 = max(0, imax - imin + 1)
		dn = n - 5 * k
		imin = max(0, (dn - a + 1) // 2)
		imax = min(dn // 2, b)
		m1 = max(0, imax - imin + 1)
		m += m5 * m1
	return m
for _ in range(int(input())):
	print(CountWays(int(input()), *map(int, input().split())))


t = int(input())
for i in range(t):
	n = int(input())
	(a, b, c, d) = list(map(int, input().split()))
	count = 0
	for i in range(0, min(2 * (b + 1), n + 1), 2):
		for j in range(0, min(5 * (c + 1), n - i + 1), 5):
			for k in range(0, min(10 * (d + 1), n - i - j + 1), 10):
				if n - i - j - k <= a:
					count += 1
	print(count)


val = [1, 2, 5, 10]
T = int(input())
for run in range(T):
	n = int(input())
	co = [int(i) for i in input().split()]
	dp = [0] * (n + 1)
	dp[0] = 1
	for i in range(4):
		for j in range(n, -1, -1):
			if dp[j] == 0:
				continue
			for k in range(1, co[i] + 1):
				if j + k * val[i] <= n:
					dp[j + k * val[i]] += dp[j]
				else:
					break
	print(dp[n])


def combswith2(N, m5, m10, result, n1, n2):
	for i in range(max([0, (N - n1) // 2]), N // 2 + 1):
		if i > n2:
			break
		elif N - 2 * i <= n1:
			result.append(0)

def combswith5(N, m10, result, n1, n2, n5):
	for i in range(max([0, (N - n1 - 2 * n2) // 5]), N // 5 + 1):
		if i > n5:
			break
		else:
			combswith2(N - 5 * i, i, m10, result, n1, n2)

def combswith10(N, result, n1, n2, n5, n10):
	for i in range(max([0, (N - n1 - 2 * n2 - 5 * n5) // 10]), N // 10 + 1):
		if i > n10:
			break
		else:
			combswith5(N - 10 * i, i, result, n1, n2, n5)
T = int(input())
for _ in range(T):
	N = int(input())
	(n1, n2, n5, n10) = list(map(int, input().split()))
	result = []
	combswith10(N, result, n1, n2, n5, n10)
	print(len(result))


def number_combi(N, array):
	c = [1, 2, 5, 10]
	K = [[1] * 5]
	for k in range(1, N + 1):
		K.append([0] * 5)
	for i in range(1, 5):
		coin = c[i - 1]
		for k in range(1, N + 1):
			q = k // coin
			bound = min(q, array[i - 1])
			s = 0
			for j in range(0, bound + 1):
				s += K[k - j * coin][i - 1]
			K[k][i] = s
	return K[N][4]
T = int(input().strip())
ar = []
S = []
for i in range(T):
	S.append(int(input().strip()))
	ar.append(list(map(int, input().strip().split(' '))))
for i in range(T):
	print(number_combi(S[i], ar[i]))


noms = [1, 2, 5, 10]

def solve(N, coins):
	L = len(coins)
	if (N, L) in D:
		return D[N, L]
	if L == 1:
		D[N, 1] = coins[0] * noms[0] >= N and N % noms[0] == 0
		return D[N, 1]
	else:
		res = 0
		for i in range(min(N // noms[L - 1], coins[L - 1]) + 1):
			res += solve(N - noms[L - 1] * i, coins[:L - 1])
		D[N, L] = res
		return res
T = int(input())
for case in range(T):
	N = int(input())
	D = {}
	coins = list(map(int, input().split()))
	print(solve(N, coins))


hist = {}
v = [1, 2, 5, 10]

def count(n, x):
	t = (n, tuple(x))
	if t in hist:
		return hist[t]
	s = sum([x[i] * v[i] for i in range(4)])
	if s < n:
		return 0
	rv = 0
	for i in range(3, -1, -1):
		if x[i] == 0:
			continue
		if n < v[i]:
			continue
		if n == v[i]:
			rv += 1
			continue
		if i == 0:
			if x[0] >= n:
				rv += 1
			continue
		x_sub = x[:]
		x_sub[i] -= 1
		for j in range(i + 1, 4):
			x_sub[j] = 0
		rv += count(n - v[i], x_sub)
	hist[t] = rv
	return rv
num_probs = int(input())
for _ in range(num_probs):
	n = int(input())
	x = [int(x) for x in input().split()]
	print(count(n, x))


def coinage(N, *args):
	mem = [0] * (N + 1)
	mem[0] = 1
	coins = [1, 2, 5, 10]
	for i in range(4):
		coin_mem = [0] * (N + 1)
		mem_copy = mem.copy()
		for j in range(coins[i], N + 1):
			if mem[j - coins[i]] > 0:
				if coin_mem[j - coins[i]] < args[i]:
					mem[j] += mem[j - coins[i]]
					coin_mem[j] = coin_mem[j - coins[i]] + 1
				elif mem[j - coins[i]] - mem_copy[j - coins[i] * (args[i] + 1)] > 0:
					mem[j] += mem[j - coins[i]] - mem_copy[j - coins[i] * (args[i] + 1)]
					coin_mem[j] = args[i]
	return mem[N]
for i in range(int(input())):
	N = int(input())
	print(coinage(N, *map(int, input().split())))


T = int(input())
for t1 in range(T):
	N = int(input())
	(A, B, C, D) = map(int, input().split())
	if A + 2 * B + 5 * C + 10 * D < N:
		print(0)
		continue
	ways = 0
	for d in range(max(0, (N - A - 2 * B - 5 * C + 9) // 10), 1 + min(D, N // 10)):
		for c in range(max(0, (N - 10 * d - A - 2 * B + 4) // 5), 1 + min(C, (N - 10 * d) // 5)):
			for b in range(max(0, (N - 10 * d - 5 * c - A + 1) // 2), 1 + min(B, (N - 10 * d - 5 * c) // 2)):
				if A >= N - 10 * d - 5 * c - 2 * b:
					ways += 1
	print(ways)


import math
T = int(input())

def subcase(t, c1, c2, n1, n2):
	minC2 = math.ceil((t - c1 * min(n1, t // c1)) / c2)
	maxC2 = min(t // c2, n2)
	result = max(maxC2 - minC2 + 1, 0)
	if c1 * n1 + c2 * n2 < t:
		result = 0
	return result
for _ in range(T):
	n = int(input())
	result = 0
	(a, b, c, d) = map(int, input().split())
	for i in range(0, n // 5 + 1):
		result += subcase(5 * i, 5, 10, c, d) * subcase(n - 5 * i, 1, 2, a, b)
	print(result)


import math
T = int(input())

def subcase(t, c1, c2, n1, n2):
	minC2 = math.ceil((t - c1 * min(n1, t // c1)) / c2)
	maxC2 = min(t // c2, n2)
	result = max(maxC2 - minC2 + 1, 0)
	return result
for _ in range(T):
	n = int(input())
	result = 0
	(a, b, c, d) = map(int, input().split())
	for i in range(0, n // 5 + 1):
		result += subcase(5 * i, 5, 10, c, d) * subcase(n - 5 * i, 1, 2, a, b)
	print(result)


import math
T = int(input())

def subcase(t, c1, c2, n1, n2):
	minC2 = math.ceil((t - c1 * min(n1, t // c1)) / c2)
	maxC2 = min(t // c2, n2)
	result = max(maxC2 - minC2 + 1, 0)
	return result
for _ in range(T):
	n = int(input())
	result = 0
	(a, b, c, d) = map(int, input().split())
	for i in range(0, n // 5 + 1):
		result += subcase(5 * i, 5, 10, c, d) * subcase(n - 5 * i, 1, 2, a, b)
	print(result)


for test in range(int(input())):
	N = int(input())
	(A, B, C, D) = map(int, input().split())
	L1 = [1] + [0 for n in range(N)]
	L2 = [0 for n in range(N + 1)]
	for n in range(N + 1):
		for a in range(min(A + 1, N - n + 1)):
			L2[n + a] += L1[n]
	L3 = [0 for n in range(N + 1)]
	for n in range(N + 1):
		for b in range(min(B + 1, (N - n) // 2 + 1)):
			L3[n + 2 * b] += L2[n]
	L4 = [0 for n in range(N + 1)]
	for n in range(N + 1):
		for c in range(min(C + 1, (N - n) // 5 + 1)):
			L4[n + 5 * c] += L3[n]
	L5 = [0 for n in range(N + 1)]
	for n in range(N + 1):
		for d in range(min(D + 1, (N - n) // 10 + 1)):
			L5[n + 10 * d] += L4[n]
	print(L5[N])


def get_count(n, a, b, c, d):
	count = 0
	for i in range(min(n // 10, d) + 1):
		for j in range(min((n - 10 * i) // 5, c) + 1):
			for k in range(min((n - 10 * i - 5 * j) // 2, b) + 1):
				if a >= n - 10 * i - 5 * j - 2 * k:
					count += 1
	return count
t = int(input().strip())
for i in range(t):
	n = int(input().strip())
	(a, b, c, d) = map(int, input().strip().split(' '))
	print(get_count(n, a, b, c, d))


import sys
import functools
coins = [1, 2, 5, 10]

def coinage(objectif, piece, quantite):
	if quantite[piece] == 0:
		return 0
	quantite[piece] -= 1
	nb = 0
	for i in range(piece, len(coins)):
		if objectif == coins[i]:
			nb += 1
		elif objectif > coins[i]:
			nb += coinage(objectif - coins[i], i, quantite)
	quantite[piece] += 1
	return nb

def subcase(t, c1, c2, n1, n2):
	minC2 = (t - c1 * min(n1, t // c1) + c2 - 1) // c2
	maxC2 = min(t // c2, n2)
	result = max(maxC2 - minC2 + 1, 0)
	return result

def coinage(n, _, q):
	(a, b, c, d) = q
	result = 0
	for i in range(0, n // 5 + 1):
		result += subcase(5 * i, 5, 10, c, d) * subcase(n - 5 * i, 1, 2, a, b)
	return result
for _ in range(int(input())):
	N = int(input())
	quantite = list(map(int, input().split()))
	print(N, quantite, file=sys.stderr)
	print(coinage(N, 0, quantite))


memo = {}

def dp(N, B, C, D):
	(B, C, D) = (min(B, N // 2), min(C, N // 5), min(D, N // 10))
	if N == 0:
		return 1
	if (N, B, C, D) in memo:
		return memo[N, B, C, D]
	res = 0
	if D:
		res = dp(N - 10, B, C, D - 1) + dp(N, B, C, 0)
	elif C:
		res = dp(N - 5, B, C - 1, 0) + dp(N, B, 0, 0)
	elif B:
		res = dp(N - 2, B - 1, 0, 0)
	memo[N, B, C, D] = res
	return res

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		(A, B, C, D) = map(int, input().split())
		res = 0
		for a in range(min(N, A) + 1):
			res += dp(N - a, B, C, D)
		print(res)
main()


import math

def subcase(t, c1, c2, n1, n2):
	mincoins = math.ceil((t - c1 * min(n1, t // c1)) / c2)
	maxcoins = min(t // c2, n2)
	return max(maxcoins - mincoins + 1, 0)
for _ in range(int(input())):
	n = int(input())
	result = 0
	(a, b, c, d) = map(int, input().split())
	for i in range(0, n // 5 + 1):
		result += subcase(5 * i, 5, 10, c, d) * subcase(n - 5 * i, 1, 2, a, b)
	print(result)


import math
T = int(input())

def subcase(t, c1, c2, n1, n2):
	minC2 = math.ceil((t - c1 * min(n1, t // c1)) / c2)
	maxC2 = min(t // c2, n2)
	result = max(maxC2 - minC2 + 1, 0)
	return result
for _ in range(T):
	n = int(input())
	result = 0
	(a, b, c, d) = map(int, input().split())
	for i in range(0, n // 5 + 1):
		result += subcase(5 * i, 5, 10, c, d) * subcase(n - 5 * i, 1, 2, a, b)
	print(result)


import math
T = int(input())

def subcase(t, c1, c2, n1, n2):
	minC2 = math.ceil((t - c1 * min(n1, t // c1)) / c2)
	maxC2 = min(t // c2, n2)
	result = max(maxC2 - minC2 + 1, 0)
	return result
for _ in range(T):
	n = int(input())
	result = 0
	(a, b, c, d) = map(int, input().split())
	for i in range(0, n // 5 + 1):
		result += subcase(5 * i, 5, 10, c, d) * subcase(n - 5 * i, 1, 2, a, b)
	print(result)


s = [1, 2, 5, 10]

def solve(N, coins):
	L = len(coins)
	if (N, L) in D:
		return D[N, L]
	if L == 1:
		D[N, 1] = coins[0] * s[0] >= N and N % s[0] == 0
		return D[N, 1]
	else:
		res = 0
		for i in range(min(N // s[L - 1], coins[L - 1]) + 1):
			res += solve(N - s[L - 1] * i, coins[:L - 1])
		D[N, L] = res
		return res
T = int(input())
for i in range(T):
	N = int(input())
	D = {}
	coins = list(map(int, input().split()))
	print(solve(N, coins))


noms = [1, 2, 5, 10]

def solve(N, coins):
	L = len(coins)
	if (N, L) in D:
		return D[N, L]
	if L == 1:
		D[N, 1] = coins[0] * noms[0] >= N and N % noms[0] == 0
		return D[N, 1]
	else:
		res = 0
		for i in range(0, int(min(N / noms[L - 1], coins[L - 1])) + 1):
			res += solve(N - noms[L - 1] * i, coins[:L - 1])
		D[N, L] = res
		return res
t = int(input())
for ijk in range(0, t):
	N = int(input())
	D = {}
	coins = list(map(int, input().strip().split()))
	print(solve(N, coins))


def countSol(coins, n):
	sol = 0
	c10 = min(n // 10, coins[3])
	c5 = min(n // 5, coins[2])
	c2 = min(n // 2, coins[1])
	for c_10 in range(0, c10 + 1):
		for c_5 in range(0, c5 + 1):
			for c_2 in range(0, c2 + 1):
				if n - c_10 * 10 - c_5 * 5 - c_2 * 2 <= coins[0] and n - c_10 * 10 - c_5 * 5 - c_2 * 2 >= 0:
					sol = sol + 1
				elif n - c_10 * 10 - c_5 * 5 - c_2 * 2 < 0:
					break
	return sol
for _ in range(int(input())):
	n = int(input())
	coins = [int(i) for i in input().split()]
	print(countSol(coins, n))


import os
import sys
import sys

def subcase(t, c1, c2, n1, n2):
	minC2 = (t - c1 * min(n1, t // c1) + c2 - 1) // c2
	maxC2 = min(t // c2, n2)
	result = max(maxC2 - minC2 + 1, 0)
	return result

def coinage(n, _, q):
	(a, b, c, d) = q
	result = 0
	for i in range(0, n // 5 + 1):
		result += subcase(5 * i, 5, 10, c, d) * subcase(n - 5 * i, 1, 2, a, b)
	return result
for _ in range(int(input())):
	N = int(input())
	quantite = list(map(int, input().split()))
	print(N, quantite, file=sys.stderr)
	print(coinage(N, 0, quantite))


import os
import sys
noms = [1, 2, 5, 10]

def solve(N, coins):
	L = len(coins)
	if (N, L) in D:
		return D[N, L]
	if L == 1:
		D[N, 1] = coins[0] * noms[0] >= N and N % noms[0] == 0
		return D[N, 1]
	else:
		res = 0
		for i in range(min(N // noms[L - 1], coins[L - 1]) + 1):
			res += solve(N - noms[L - 1] * i, coins[:L - 1])
		D[N, L] = res
		return res
T = int(input())
for case in range(T):
	N = int(input())
	D = {}
	coins = list(map(int, input().split()))
	print(solve(N, coins))


import math
T = int(input())

def subcase(t, c1, c2, n1, n2):
	minC2 = math.ceil((t - c1 * min(n1, t // c1)) / c2)
	maxC2 = min(t // c2, n2)
	result = max(maxC2 - minC2 + 1, 0)
	return result
for _ in range(T):
	n = int(input())
	result = 0
	(a, b, c, d) = map(int, input().split())
	for i in range(0, n // 5 + 1):
		result += subcase(5 * i, 5, 10, c, d) * subcase(n - 5 * i, 1, 2, a, b)
	print(result)