SMM數

題目敘述

$SM$數列是這樣定義的: $$ SM(x)=\left\{ \begin{array}{rcl} 1, & & {x=1 \; or \; x=2}\\ SM(x-1)+SM(x-2), & & {x > 2} \end{array} \right. $$ 如果某個$SM$數與任何比他小的$SM$數互質，那麼稱他為$SMM$數。最小的$SMM$數是2，第二小的是3，第三小的是5，之後是13...。

給一個正整數n，請問$SM(1)$到$SM(n)$中有幾個$SMM$數?

輸入說明

輸入有多比測資，第一行一個數字$n,\;1\leq n \leq 10^6$，表示詢問。當$n=0$表示輸入結束，你不必對這筆資料作處理。

輸出說明

對於每組測試資料請先輸出這是第幾個數列，然後是SMM數的總數。

詳請見範例輸入輸出

範例輸入

1
2
3
4
5
0

範例輸出

Case #1: 0
Case #2: 0
Case #3: 1
Case #4: 2
Case #5: 3

配分方法

• 10% $n \leq 100$
• 20% $n \leq 1000$
• 30% $n \leq 10^4$
• 40% $n \leq 10^6$

Hints

備註

Judge Setting