coins-32

Ahmed found a bag having many coins in it of ₹1, ₹2, ₹5 and ₹10. One of his best friend Abdul need ₹R urgently so he asked Ahmed for it. Ahmed want to know all the possibilities in which he can give money to Abdul using all coins which are with him.
Your task is to find out number of ways in which total money can be given with using available coins only i.e,. in how many ways we can sum them(coins) up to form a total of ₹R.

Input Format:

The first line contains an integer T which is number of test cases. Each test case contains 2 lines. The first line contains integer R (Rupee 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 R

Constraints:

1 ≤ T ≤ 200 

1 ≤ R ≤ 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

For case 1 we need to find the different ways to get sum total to 15. So we can use one ₹10 coin and one ₹5 coin or we can use one ₹10 coin two ₹2 coin and one ₹1 coin. So, 2 ways to achieve this.

For case 2 we need to find the different ways to get sum total to 12. So we can use one ₹10 coin and one ₹2 coin or we can use one ₹10 coin two ₹1 coin. So, there are 2 ways to achieve this.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY
Tags: Dynamic programming

Mathematics


Solutions: