C++ or Java

Denominations

You are working at a cash counter at walmart and you have infinite number of 3, 5 and 10 denomination coins. Can you determine the number of ways of making change for a particular number of units using the given types of coins?

Input: The first line contains an Integer T, the number of test cases. Next T lines contain a single integer N.

Output: For each test case, print the number of ways you can form a sum of N by using the coin denominations.

Constraints: 1T103 0N106

Sample Input

2 20 13 

Sample Output

4 2

Explanation

Case 1: N=20. There are 4 ways to make a sum of 20 using 3, 5 and 10 denomination coins. They are (10, 10), (5, 5, 10), (5, 5, 5, 5), (3, 3, 3, 3, 3, 5) Case 2: N=13. There are 2 ways to make a sum of 20 using 3, 5 and 10 denomination coins. They are (3, 5, 5), (3, 10)

Note: Your code should be able to convert the sample input into the sample output. However, this is not enough to pass the challenge, because the code will be run on multiple test cases. Therefore, your code must solve this problem statement.