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.
Input
The first line contains the number of testcases t (1 ≤ t ≤ 100). The i-th of the following t lines contains one integer ni (1 ≤ ni ≤ 1018).
Output
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 ni and its complexity, separated with space.
Sample
input | output |
---|
5
1
10
100
1000
10000
| 1 1
6 4
60 12
840 32
7560 64
|
Problem Author: Petr Lezhankin
Problem Source: Ufa SATU Contest. Petrozavodsk Summer Session, August 2009