Coin Combinations

You are given coins of denominations (1), (2), and (5). Your task is to calculate the number of distinct ways to form a given target amount using these coins. Note that the order of coins does not matter, and each coin denomination can be used any number of times.

For example, for a target of (5), there are 4 distinct combinations: ( 5 = 1+1+1+1+1) (5 = 1+1+1+2) (5 = 1+2+2) (5 = 5) )

Furthermore, you need to process multiple queries. The input begins with an integer (N) representing the number of queries. The following (N) lines each contain one integer, representing a target amount. For each target amount, output the number of valid coin combinations on a separate line.

inputFormat

The first line of input contains a single integer (N), the number of queries. Each of the following (N) lines contains one integer (target) ((0 \le target \le 10^4)), which represents the amount for which you have to find the number of coin combinations.

outputFormat

For each target amount, print the number of distinct ways to form that amount using coins of denominations (1), (2), and (5) on a new line.## sample

3
5
10
0

4
10
1