In the country of Numberia, there is a city called Coinsland. Today there is a fair in the city. Abhishek is very excited about it. He visits a stall that sells toys with price ranging from 1 to n inclusive.

He wants to buy all of them. He has coins of denomination 3 in his left pocket and coins of 5 in his right pocket. To buy a particular toy, he decides to use only a single type of coin.

As you are with him, you have to help him to know exactly how many toys he can purchase.

NOTE: Number of coins are infinite. Keep in mind that there is only one toy of each price.

Input

First line of the input consists of number of test cases T (<= 15). Next T lines contains numbers n.

Output

Output should contain a number which is the total number of toys which Abhishek can buy.

Constraints

n <= 10^9

Example

Input:
1
20

Output:
9