Q10680: LCM

你們都知道 LCM（Least Common Multiple）吧，就是最小公倍數啦！例如：4 和 6 的 LCM 是12。LCM 也可以定義不只2個數。例如：2, 3, 5 的 LCM 是 30。同樣的，我們也可以定義前 N 個整數的 LCM。例如：前 6 個整數的 LCM 是 60。

你會發現隨著 N 的增加，LCM 會成長的非常快。所以我們並沒有興趣在 1 到 N 真正的 LCM 值上。但是我們想要知道它最後一位不為 0 的數是多少。例如：N=6, 前6個整數的 LCM 真正的值為 60, 但是你只要告訴我 6 就可以了。若N=7， 前7個整數的 LCM 真正的值為 420, 但是你只要告訴我 2 就可以了。

請你要有效率的找呦。

Input

輸入含有多組測試資料（不會超過1000組）。

每組測試資料一列。含有1個正整數 N（ 1 <=  N <= 1000000）。若N=0，代表輸入結束。

Output

對每組測試資料輸出一列，前 N 個整數的 LCM 的最後一位不為 0 的數是多少。