入力

入力は以下の形式で標準入力から与えられる。

Q
n_1
:
n_Q

• 1 行目には、クエリの数 Q が与えられる。
• 2行目からQ行にわたって、整数 nが与えられる。
• n_iとは、i回目のクエリにおけるnを表す。

出力

出力は以下の形式で標準出力に従うこと。

• n以下の整数の中で最大の約数の個数と、その約数の個数を持つ数のなかで最小の整数を空白区切りで出力すること。
• 例えばn=96のとき、約数が12個の数字は60,72,84,90,96の5つありますが、その中で最小の60を最小の整数として出力します。
• この場合、この行は"12 60"という出力となります。
• 各クエリごとに出力するため、出力はQ行からなる。

制約

• 1≦n≦{10}^{17}
• 1≦Q≦1,000

小課題

小課題 1 [ 8 点 ]

• 1≦n≦10,000を満たす。

• Q≦100を満たす。

小課題 2 [ 34 点 ]

• 1≦n≦1,000,000,000を満たす。

• Q≦100を満たす。

小課題 3 [ 58 点 ]

• 追加の制約はない。