Context

You probably know the famous TV game show: "Cifras y Letras" in Spain, "CountDown" in UK, "Cijfers en Letters" in Nederland, "Tik Tak" in Israel, "A word or 2" in South Africa, etc., etc., and, of course, the original "Des Chiffres et des Lettres" broadcasted in France since 1972!

The game of the numbers --that is, obtain a target number by combining a tuple of input numbers with the four basic arithmetic operations-- is an all-time classic in TV contests worldwide, and also in the science of computer algorithms. Nowadays, any computer science student should be able to write a program that solves the problem in half a second on any off-the-shelf computer. So, let's make it a bit more difficult...

The Problem

In the original game of the numbers, called "Le compte est bon", the player is given a tuple of 6 input numbers, and a target number. The purpose is to combine input numbers (all or some of them, but not repeating any input number) with the basic arithmetic operations "+", "-", "*" and "/" (always working with integer and positive numbers), in order to obtain the target number. The input numbers can be: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75, 100.

If the target number can be obtained with the input tuple, then we will say that the tuple generates the target. For example, the tuple (6, 4, 25, 6, 1, 100) generates the target 574 (among many other targets) with: 6*100-25-1 = 574; but that tuple does not generate the target 765 (i.e., it is not possible to obtain that number with the input tuple).

In this problem, we will invert the original game: we only know the target number. You have to compute how many different input tuples generate that target. For example, the target 1 can be generated with all input tuples, so the solution would be 14⁶ = 7 529 536. Observe that we suppose that, for example, tuples: (1, 2, 3, 4, 5, 6) and (6, 5, 4, 3, 2, 1) are different.

The Input

The first line of the input contains an integer N, indicating the number of test cases. For each test case, there is a line with an integer, between 1 and 8000, indicating the target number.

The Output

For each test case, the output should consist of an integer, representing the total number of different tuples that generate the corresponding target.

Sample Input

2
1
8000

Sample Output

7529536
5838170

OMP'09
Facultad de Informatica
Universidad de Murcia (SPAIN)