Pair of Coprime Numbers

2 secs 1024 MB
magurofly

問題文


青木くんはからくり仕掛けを作ろうとしています。

からくり仕掛けには歯車が必要ですが、歯車の損耗を抑えるためには噛み合う歯車の歯の数は互いに素である必要があります。

青木くんは高橋くんにそのような歯車の組合せがどれだけありうるか聞いてみることにしました。


正整数 が与えられます。

以下の正整数のペア のうち、 であるものの数を求め、 で割ったあまりを答えてください。

ただし、順序を交換したペア、つまり、 は同じものとみなします。

制約


  • 入力は整数である

入力


出力


答えを 行に出力せよ。

入出力例


入力例1
4
出力例1
6

以下の互いに素なペアには があります。

入力例2
10
出力例2
32

個のペアが存在します。

Submit


Go (1.14)