ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1748. The Most Complex Number

Time limit: 1.0 second
Memory limit: 64 MB
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

inputoutput
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