Let’s talk about one fascinating fact about circles. For that, let’s perform the following experiment:

Take any circle, it can be big or small.

Measure it’s circumference. Denote the length of the circumference by C.

Measure the diameter of the circle. Denote the length of the diameter by D.

Measure C/D by calculating the result after dividing C with D.

If you perform the above three steps with different circles, you will always end up finding the exact same value in step 4. The constant found at step 4 is called Pi. The number of digits increases infinitely after the decimal point. But for many practical uses, we only take digits up to certain places after the decimal point. For example, the approximate value up to five decimal places for Pi would be 3.14159.

In this problem, you will be given a number x, you will have to print the sum of the digits of Pi up to x decimal places.

Input

In this problem, you will be given a number $x$, you will have to print the sum of the digits of Pi up to $x$ decimal places.

The first line of input will have $T$ ( $1 <= T <= 15$ ), the number of test cases.

In each of the next $T$ lines, there will be an integer $x$ ( $0 <= x <= 15$ ), the sum of digits after the decimal places up to which you will have to print as a result.

There is no sub-task for this problem, you will have to solve each cases completely to get the full points.

Output

For each input $x$, print an integer on a line, the intended sum.

Sample

Input

Output

2
0
1

0
1

The following code can be used to print some of the digits of Pi: