Let us define a complexity of an integer as the number of its divisors. Your task is to find the most complex integer in range from 1 to n. If there are many such integers, you should find the minimal one.

The first line contains the number of testcases t (1 ≤ t ≤ 100). The i-th of the following t lines contains one integer n_i (1 ≤ n_i ≤ 10¹⁸).

For each testcase output the answer on a separate line. The i-th line should contain the most complex integer in range from 1 to n_i and its complexity, separated with space.