百度之星題--斐波拉契數列

題目：

du熊學斐波那契i

time limit : 2000/1000ms (c/other) memory limit :

65535/32768k (c/other)

本次組委會推薦使用c、c++

problem description

du熊對數學一直都非常感興趣。最近在學習斐波那契數列的它，向你展示了一個數字串，它稱之為“斐波那契”串：

11235813471123581347112358........

聰明的你當然一眼就看出了這個串是這麼構造的：1.先寫下兩位在0~9範圍内的數字a,

b，構成串ab；2.取串最後的兩位數字相加，将和寫在串的最後面。

上面du熊向你展示的串就是取a = b = 1構造出來的串。

顯然，步驟1之後不停地進行步驟2，數字串可以無限擴充。現在，du熊希望知道串的第n位是什麼數字。

input

輸入資料的第一行為一個整數t（1 <= t <= 1000）, 表示有t組測試資料；

每組測試資料為三個正整數a, b, n（0 <= a, b < 10, 0 < n <= 10^9）。

output

對于每組測試資料，輸出一行“case #c: ans”（不包含引号）

c是測試資料的組數，從1開始。

sample input

3

1 1 2

1 1 8

1 4 8

sample output

case #1: 1

case #2: 3

case #3: 9

hint

對于第一、二組資料，串為112358134711235......

對于第三組資料，串為14591459145914......

我随筆寫了點代碼，因為我很少去訓練這樣的競賽題，歡迎指點。

複雜度為o(n),n為一百萬時運作時間也基本上幾ms（vc2008、win7,2g）。