There are four types of common coins in US currency: quarters (25 cents), dimes (10), nickels (5) and pennies (1). There are 6 ways to make change for 15 cents:
- A dime and a nickel;
- A dime and 5 pennies;
- 3 nickels;
- 2 nickels and 5 pennies;
- A nickel and 10 pennies;
- 15 pennies.
How many ways are there to make change for C cents using these common coins?
Input/Output
You will be given N the number of cases. N lines follow, which each contain a single integer C, the number of cents. Print out the number of ways to make change of C cents.
