TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2376
  • 問題
  • P2376【NOIP无压力模拟赛5】蜘蛛展览
    制限 : 時間制限 : 10000 MS   メモリ制限 : 265536 KB
    問題説明

    话说育母蜘蛛搞了一批小蜘蛛……于是育母蜘蛛要跟小蜘蛛们玩个游戏……育母蜘蛛让小蜘蛛们按照 1 到K 的顺序报数,报完K 后再报 1,每次报K 的小蜘蛛就会受到惩罚,小蜘蛛们在报数之前就 知道谁要受惩罚,于是一些小蜘蛛结成了同盟,小蜘蛛的同 盟很有意思,两只小蜘蛛是同盟当且仅当两只小蜘蛛的最大公约数不为 1。

    现在育母蜘蛛要带一些小蜘蛛去参加展览,育母蜘蛛希望带的 小蜘蛛里任意两只都不是同盟,现在育母蜘蛛想知道它最多能带多少 只小蜘蛛,在个数最多的情况下,育母蜘蛛还想知道所带的小蜘蛛总 的编号和最小是多少。

    入力形式

    第一行一个数 T,表示数据组数
    接下来T 行,每行一个数字N,表示小蜘蛛的数量

    出力形式

    T行,每行两个数,用空格隔开,表示两个问题的答案。

    サンプル入力

    2
    3
    9

    サンプル出力

    3 6
    5 18

    ヒント

    T≤100000,N≤10000000


    ソース  hzoi