對一個分數 m/n 來說，如果gcd(m,n)=1我們說它是不可約分的（irreducible）。給你一個正整數n，在這個問題中，請你找出共有幾個不可約分的真分數。
例如：n=12，在還沒約分之前你可以有以下12個真分數
經過約分後可以得到以下12個真分數
所以可以知道共有以下4個不可約分的真分數
Input
每筆測試資料一列，包含1個正整數 n（< 1000000000）。n=0代表輸入結束。
Output
對每一列測試資料，請輸出共有幾個不可約分的真分數。
Sample input
1 2 3 12 123456 7654321 0
Sample Output
1 1 2 4 41088 7251444