數學界中，黎曼假設 (Riemann Hypothesis)被數學家們稱之為最大為解決的難題之一：「對於所有黎曼 ζ 函數 (zeta function) 中非平凡零點 (non-trivial zeros) 的實數部分是二分之一。」那麼現在給你一個很簡單的題目：對於每個正整數 N，請輸出第 N 個零點 … 呵，開玩笑的！這樣子這道題目會變得太複雜，我們可以選擇計算比較簡單而且跟黎曼函數相關的梅登函數 (Mertens’s function)。如果有興趣想要知道的話，請參閱 Derbyshire 的書 (見後記)。

對於每個大於 1 的正整數，我們可以把它質因數分解。有些數字像 2、7、11 等只有一個因數的數，我們稱它為質數 (prime numbers)。其他數字像 4 (2×2)、15 (3×5)、144 (2^4×3^2) 我們稱它為合數 (composite numbers)。如果一個數的每個質因數都只有一個，我們稱它為 square free，有些合數像 21 (3×7)、187 (11×17) 就是 square free，而有些合數像 9 (3^2)、98 (2×7^2) 則不是。

於是我們先定義默比烏斯函數 (Möbius function) 為 mu(N)，對於每個正整數 N：

定義 mu(N) = 1；
如果 N 不是 square free，那 mu(N) = 0；
如果 N 是 square free，而且它有偶數個質因數，那麼 mu(N) = 1；
如果 N 是 square free且有奇數個質因數，那麼 mu(N) = -1。

接著，我們可以定義梅登函數 (Mertens’s function) M(N)為默比烏斯函數從 1 到 N 的級數和：
M(N) = mu(1) + mu(2) + … + mu(N)。

下列為前 20 個默比烏斯函數及梅登函數的值：

N	質因數	mu(N)	M(N)
1	-	1	1
2	2	-1	0
3	3	-1	-1
4	2 2	0	-1
5	5	-1	-2
6	2 3	1	-1
7	7	-1	-2
8	2 2 2	0	-2
9	3 3	0	-2
10	2 5	1	-1
11	11	-1	-2
12	2 2 3	0	-2
13	13	-1	-3
14	2 7	1	-2
15	3 5	1	-1
16	2 2 2 2	0	-1
17	17	-1	-2
18	2 3 3	0	-2
19	19	-1	-3
20	2 2 5	0	-3

請求出對於一正整數 N 的 mu(N) 和 M(N)。

Input

輸入每行包括一個正整數 N (N 介於 1 至 1000000)。輸入測資以 0 作為結束，這行不需被處理。

Output

對於每個正整數 N，請依序輸出 N、mu(N)、M(N)在一行，每個輸出數字的寬度為 8。

Sample Input

Output for Sample Input

 20       0      -3
  1       1       1
144       0      -1
 73      -1      -4

後記 (不影響解題)

一個 ζ 函數 (zeta function) 可以被定義成下面的無窮級數：
zeta(s) = 1 + 2^(-s) + 3^(-s) + 4^(-s) + …

其中s為任意複數。

ζ 函數擁有許多零點 (zeros) (註：零點代表 zeta(s) = 0)，其中有些為非平凡零點 (non-trivial ones)，黎曼在 1859 年臆測這些非平凡零點的實部恆為二分之一，而虛部可為任意值。到目前為止，許多非平凡零點都被找到，可是沒有一個人能夠證明 (或否定) 黎曼的假設是否是對的。這個著名的黎曼假設在數學上的各個領域都有其延伸定理，這些定理都是根據黎曼假設為真的情況下成立，所以如果有人能夠證明黎曼假設是錯的 (一個反例就夠了)，那麼現代數學也會因此而崩潰！

有一個方法可以證明黎曼猜想，那就是從梅登函數的定義 (Mertens’s function)，我們可以證明梅登函數與 N 的平方高度相關：M(N) = O(N^(1/2))

其中 O 代表大 O 符號 (big-oh notation)，意思是當 N 極大時，M(N)的絕對值會相當接近而不超過 N^(1/2) (譯者註：漸近)。雖然這項定理尚未證明，但如果這項定理是對的，那麼黎曼假設也會是對的 (不要問我為什麼)。

欲知更多詳情，請參閱 John Derbyshire 所著的「Prime Obsession」這本書。