TopCoder

User's AC Ratio

100.0% (35/35)

Submission's AC Ratio

38.2% (55/144)

Tags

Description

冒險由此開始
在一個雨疏風驟的夜晚,妁艷吃著棒棒糖撐著傘準備過馬路。
吸著棒棒糖的妁艷吸阿吸的~忽然一道炫目的閃光閃入了他的眼中。抬起頭往右一看,只見貌似車頭燈的東西發出了無比耀眼的光芒。
妁艷立即以反射的速度按出了”↑↑↓↓←→←→BA”!
可惜閃光越來越近,仍不見有英雄來相救,妁艷就這樣仆街了……

「吃東西囉~來妁艷起來吃東西囉~」甜美的聲音在妁艷耳邊繚繞著。
「唔…唔…唔……」妁艷勉強的睜開了眼睛,想說自己到底是在天堂還是哪裡……

吃完東西後,妁艷的HP跟MP回復了滿點!這時他才知道原來剛剛他根本沒被撞到,而是因為過於驚嚇而昏倒了……雖然妁艷覺得在吃完東西之後他已經完全康復了,可是護士姊姊依然堅持要做些檢查……

只見護士拿出了一疊卡片,分別寫著「1、2、3、5、8……」各有一張。
妁艷一看,毫不猶豫就說「這不就費氏數列嗎!?」
原來護士是想測試看看控制傳說中的(咳~)的大腦運作是否正常,所以要測試看看妁艷是否因為過度的驚嚇導致腦部的受創,更甚者……不再是妁艷了。
現在護士會說出一個數字K,想問究竟妁艷必須要至少拿幾張卡片,才能使得這些卡片的和為K呢?亦或者根本無法用這些卡來湊出這個數字K呢?

Input Format

第一行為一個正整數N,代表共有幾筆輸入
N<=100000
之後2~N+1行每行有一個數字K(K保證可用有號int儲存)

Output Format

請針對每組輸入,輸出妁艷最少要拿出幾張卡片才有辦法湊出K?
如果說無法湊出K,請輸出"iyada~"(不含雙引號)
(詳細輸出情參考Sample Output)

Sample Input

5
1
2
3
5
8

Sample Output

1
1
1
1
1

Hints

可用點數學歸納法驗證自己的猜想

Problem Source

原TIOJ1751 / problem setter:jeremy89183

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 50
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536