SORTMUCH - How many can you sort?

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

Added by:cegprakash
Date:2016-11-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: BF GOSU

hide comments
2017-08-05 00:21:40
For want-to-be solvers that are wondering: I got AC using built-in c++ log().
2016-12-17 14:48:39 Vipul Srivastava
Finally...
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.