Lets define the complexity of the number as the number of its divisors. Find among the numbers from 1 to n the most complex number. If there are several such numbers, find the smallest of them.

Input

First line contains the number of test cases t (1 ≤ t ≤ 100). Each of the next t lines contains one integer n (1 ≤ n ≤ 1018).

Output

For each test case print in a separate line the most complex number from 1 to n and its complexity.