Problem Description

著名出题人小Q出过非常多的题目，在这个漫长的过程中他发现，确定题目的数据范围是非常痛苦的一件事。

每当思考完一道题目的时间效率，小Q就需要结合时限以及评测机配置来设置合理的数据范围。

因为确定数据范围是一件痛苦的事，小Q出了非常多的题目之后，都没有它们设置数据范围。对于一道题目，小Q会告诉你他的算法的时间复杂度为$O(n^a\log^bn)$，且蕴含在这个大$O$记号下的常数为$1$。同时，小Q还会告诉你评测机在规定时限内可以执行$k$条指令。小Q认为只要$n^a\left(\lceil\log_2n\rceil\right)^b$不超过$k$，那么就是合理的数据范围。其中，$\lceil x\rceil$表示最小的不小于$x$的正整数，即$x$上取整。

自然，小Q希望题目的数据范围$n$越大越好，他希望你写一个程序帮助他设置最大的数据范围。

Input

第一行包含一个正整数$T(1\leq T\leq 1000)$，表示测试数据的组数。

每组数据包含一行三个正整数$a,b,k(1\leq a,b\leq 10,10^6\leq k\leq 10^{18})$，分别描述时间复杂度以及允许的指令数。

Output

对于每组数据，输出一行一个正整数$n$，即最大可能的$n$。

3
1 1 100000000
2 1 100000000
1 3 200000000

4347826
2886
48828