You have invented a new sorting algorithm which can sort n integers in exactly n log3 n time. (which is faster than almost every sorting algorithm till date). You have proved the correctness of your algorithm to your professor.

The professor now asks you what is the maximum number of integers that you can sort in a given time T.

Note: log3 = (log to the base 3)

Proper usage of type casting is required to solve this problem. For testing purposes you can use this high precision calculator.

Input:

The first line consists of an integer t. For each test case, you are given an integer T, the time to sort the integers.

Output:

For each test case, print the maximum number of integers that you can sort in T time.

Constraints:

1 <= t <= 10^5

3 <= T <= 10^10

Time limit: 1 second

Example:

Input:
4
3
10
10000000000
4374
Output:
3
6
546076908
729