D - 2016

Time Limit: 3 sec / Memory Limit: 128 MB

問題文

今年の 85 日から, リオデジャネイロオリンピックが開催される。

夏季オリンピックは, 4 の倍数の年に開催されることになっている。

また, 今年の 526 日に, 伊勢志摩サミットが開催される。

日本で開催されるサミットは, 2000, 2008, 2016,... 年と, 近年では 8の倍数となっている。

とにかく, 今年は「約数が多い」。なんと, 36 個もの約数があるのだ。

これは, 世の中のだれもが思っていることであろう。なぜなら, このような「約数の多い年」は, めったに経験しないことであるからだ。

中学 2 年生の私でさえ, これを重く受け止めているのであるから。

そこで, 私は皆さんに次のような問題を出す。

1 以上 n 以下の整数の中で, 最も約数が多い数と, その約数の個数を求めなさい。」

未来の人々のためにも, この問題を解いてあげましょう。

入力

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

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

出力

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

  • n以下の整数の中で最大の約数の個数と、その約数の個数を持つ数のなかで最小の整数を空白区切りで出力すること。
  • 例えばn=96のとき、約数が12個の数字は60,72,84,90,965つありますが、その中で最小の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 点 ]

  • 追加の制約はない。

入力例1

1
50

出力例1

10 48

48の約数は{1,2,3,4,6,8,12,16,24,48}の10個である。

入力例2

1
96

出力例2

12 60

問題文中の例と同じである。

入力例3

3
240
480
1200

出力例3

20 240
24 360
32 840

8401から8まですべて割り切れる最小の数である。

また、出力はクエリごとに改行することに注意せよ。

入力例4

2
2016
423

出力例4

40 1680
24 360

2016はとても約数が多いが、1680の約数の個数にはかなわない。

また、今日は2016423日である。ちなみに、423の約数の個数は6個である。

問題文担当者:E869120