시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1414 808 652 55.918%

문제

피보나치 수 ƒK는 ƒK = ƒK-1 + ƒK-2로 정의되며 초기값은 ƒ0 = 0과 ƒ1 = 1 이다. 양의 정수는 하나 혹은 그 이상의 서로 다른 피보나치 수들의 합으로 나타낼 수 있다는 사실은 잘 알려져 있다. 

하나의 양의 정수에 대한 피보나치 수들의 합은 여러 가지 형태가 있다. 예를 들어 정수 100은 ƒ4 + ƒ6 + ƒ11 = 3 + 8 + 89 또는 ƒ1 + ƒ3 + ƒ6 + ƒ11 = 1 + 2 + 8 + 89, 또는 ƒ4 + ƒ6 + ƒ9 + ƒ10 = 3 + 8 + 34 + 55 등으로 나타낼 수 있다. 이 문제는 하나의 양의 정수를 최소 개수의 서로 다른 피보나치 수들의 합으로 나타내는 것이다. 

하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라. 

입력

입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n이 주어진다. 단, 1 ≤ n ≤ 1,000,000,000. 

출력

출력은 표준출력을 사용한다. 하나의 테스트 데이터에 대한 해를 하나의 줄에 출력한다. 각 테스트 데이터에 대해, 피보나치 수들의 합이 주어진 정수에 대해 같게 되는 최소수의 피보나치 수들을 증가하는 순서로 출력한다. 

예제 입력 1

4
100
200
12345
1003

예제 출력 1

3 8 89
1 55 144
1 34 377 987 10946
3 13 987
W3sicHJvYmxlbV9pZCI6IjkwMDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMTggJmZub2Y7PHN1Yj5LPFwvc3ViPlx1YjI5NCAmZm5vZjs8c3ViPks8XC9zdWI+ID0gJmZub2Y7PHN1Yj5LLTE8XC9zdWI+ICsgJmZub2Y7PHN1Yj5LLTI8XC9zdWI+XHViODVjIFx1YzgxNVx1Yzc1OFx1YjQxOFx1YmE3MCBcdWNkMDhcdWFlMzBcdWFjMTJcdWM3NDAgJmZub2Y7PHN1Yj4wPFwvc3ViPiA9IDBcdWFjZmMgJmZub2Y7PHN1Yj4xPFwvc3ViPiA9IDEgXHVjNzc0XHViMmU0LiBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViMjk0IFx1ZDU1OFx1YjA5OCBcdWQ2MzlcdWM3NDAgXHVhZGY4IFx1Yzc3NFx1YzBjMVx1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWI0ZTRcdWM3NTggXHVkNTY5XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0XHViMjk0IFx1YzBhY1x1YzJlNFx1Yzc0MCBcdWM3OTggXHVjNTRjXHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+XHVkNTU4XHViMDk4XHVjNzU4IFx1YzU5MVx1Yzc1OCBcdWM4MTVcdWMyMThcdWM1ZDAgXHViMzAwXHVkNTVjIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWI0ZTRcdWM3NTggXHVkNTY5XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzAgXHVkNjE1XHVkMGRjXHVhYzAwIFx1Yzc4OFx1YjJlNC4gXHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCBcdWM4MTVcdWMyMTggMTAwXHVjNzQwICZmbm9mOzxzdWI+NDxcL3N1Yj4gKyAmZm5vZjs8c3ViPjY8XC9zdWI+ICsgJmZub2Y7PHN1Yj4xMTxcL3N1Yj4gPSAzICsgOCArIDg5IFx1YjYxMFx1YjI5NCAmZm5vZjs8c3ViPjE8XC9zdWI+ICsgJmZub2Y7PHN1Yj4zPFwvc3ViPiArICZmbm9mOzxzdWI+NjxcL3N1Yj4gKyAmZm5vZjs8c3ViPjExPFwvc3ViPiA9IDEgKyAyICsgOCArIDg5LCBcdWI2MTBcdWIyOTQgJmZub2Y7PHN1Yj40PFwvc3ViPiArICZmbm9mOzxzdWI+NjxcL3N1Yj4gKyAmZm5vZjs8c3ViPjk8XC9zdWI+ICsgJmZub2Y7PHN1Yj4xMDxcL3N1Yj4gPSAzICsgOCArIDM0ICsgNTUgXHViNGYxXHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM3NzQgXHViYjM4XHVjODFjXHViMjk0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM1OTFcdWM3NTggXHVjODE1XHVjMjE4XHViOTdjIFx1Y2Q1Y1x1YzE4YyBcdWFjMWNcdWMyMThcdWM3NTggXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViNGU0XHVjNzU4IFx1ZDU2OVx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWQ1NThcdWIwOThcdWM3NTggXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNTggXHVjMjE4XHViNGU0XHVjNzU4IFx1ZDU2OVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzQgXHVjODE1XHVjMjE4XHVjNjQwIFx1YWMxOVx1YWM4YyBcdWI0MThcdWIyOTQgXHVjZDVjXHVjMThjIFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OCBcdWMyMThcdWI0ZTRcdWM3NDQgXHVhZDZjXHVkNTU4XHViNzdjLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWQ0NWNcdWM5MDBcdWM3ODVcdWI4MjVcdWM3NDQgXHVjMGFjXHVjNmE5XHVkNTVjXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NDAgVCBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IFQgXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM1ZDBcdWIyOTQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzgxNVx1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU4LCAxICZsZTsgbiAmbGU7IDEsMDAwLDAwMCwwMDAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFx1ZDQ1Y1x1YzkwMFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHVjNWQwIFx1YjMwMFx1ZDU1YyBcdWQ1NzRcdWI5N2MgXHVkNTU4XHViMDk4XHVjNzU4IFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YjRlNFx1Yzc1OCBcdWQ1NjlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YzgxNVx1YzIxOFx1YzVkMCBcdWIzMDBcdWQ1NzQgXHVhYzE5XHVhYzhjIFx1YjQxOFx1YjI5NCBcdWNkNWNcdWMxOGNcdWMyMThcdWM3NTggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1YzIxOFx1YjRlNFx1Yzc0NCBcdWM5OWRcdWFjMDBcdWQ1NThcdWIyOTQgXHVjMjFjXHVjMTFjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5MDA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmlib25hY2NpIE51bWJlcnMiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBGaWJvbmFjY2kgbnVtYmVyICZmbm9mOzxzdWI+SzxcL3N1Yj4gaXMgZGVmaW5lZCBieSAmZm5vZjs8c3ViPks8XC9zdWI+ID0gJmZub2Y7PHN1Yj5LLTE8XC9zdWI+ICsgJmZub2Y7PHN1Yj5LLTI8XC9zdWI+IHdpdGggc2VlZCB2YWx1ZXMgJmZub2Y7PHN1Yj4wPFwvc3ViPiA9IDAsICZmbm9mOzxzdWI+MTxcL3N1Yj4gPSAxLiBJdCBpcyBrbm93biB0aGF0IGV2ZXJ5IHBvc2l0aXZlIGludGVnZXIgY2FuIGJlIHJlcHJlc2VudGVkIGFzIHRoZSBzdW0gb2Ygb25lIG9yIG1vcmUgZGlzdGluY3QgRmlib25hY2NpIG51bWJlcnMuIFRoZXJlIGFyZSBtYW55IGRpZmZlcmVudCByZXByZXNlbnRhdGlvbnMgb2YgRmlib25hY2NpIHN1bXMgZm9yIGEgcG9zaXRpdmUgaW50ZWdlci4gRm9yIGV4YW1wbGUsIEZpYm9uYWNjaSBzdW1zIGZvciAxMDAgY2FuIGJlIHJlcHJlc2VudGVkIGJ5ICZmbm9mOzxzdWI+NDxcL3N1Yj4mbmJzcDsrICZmbm9mOzxzdWI+NjxcL3N1Yj4mbmJzcDsrICZmbm9mOzxzdWI+MTE8XC9zdWI+Jm5ic3A7PSAzICsgOCArIDg5IG9yICZmbm9mOzxzdWI+MTxcL3N1Yj4mbmJzcDsrICZmbm9mOzxzdWI+MzxcL3N1Yj4mbmJzcDsrICZmbm9mOzxzdWI+NjxcL3N1Yj4mbmJzcDsrICZmbm9mOzxzdWI+MTE8XC9zdWI+Jm5ic3A7PSAxICsgMiArIDggKyA4OSwgb3IgJmZub2Y7PHN1Yj40PFwvc3ViPiZuYnNwOysgJmZub2Y7PHN1Yj42PFwvc3ViPiZuYnNwOysgJmZub2Y7PHN1Yj45PFwvc3ViPiZuYnNwOysgJmZub2Y7PHN1Yj4xMDxcL3N1Yj4mbmJzcDs9IDMgKyA4ICsgMzQgKyA1NSBldGMuIEluIHRoaXMgcHJvYmxlbSwgd2Ugd2FudCB0byBmaW5kIHRoZSBtaW5pbXVtIG51bWJlciBvZiBGaWJvbmFjY2kgbnVtYmVycyBmb3IgYW4gaW50ZWdlci48XC9wPlxyXG5cclxuPHA+Rm9yIGEgZ2l2ZW4gcG9zaXRpdmUgaW50ZWdlciwgZmluZCB0aGUgbWluaW11bSBudW1iZXIgb2YgZGlzdGluY3QgRmlib25hY2NpIG51bWJlcnMgd2hvc2Ugc3VtIGlzIGVxdWFsIHRvIHRoZSBnaXZlbiBudW1iZXIuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGNvbnRhaW5zIG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIG4gLCB3aGVyZSAxICZsZTsgbiAmbGU7IDEsMDAwLDAwMCwwMDAuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+WW91ciBwcm9ncmFtIGlzIHRvIHdyaXRlIHRvIHN0YW5kYXJkIG91dHB1dC4gUHJpbnQgZXhhY3RseSBvbmUgbGluZSBmb3IgZWFjaCB0ZXN0IGNhc2UuIFRoZSBsaW5lIHNob3VsZCBjb250YWluIHRoZSBGaWJvbmFjY2kgbnVtYmVycyBpbiBpbmNyZWFzaW5nIG9yZGVyIHdoaWNoIHN1bSBpcyBlcXVhbCB0byB0aGUgZ2l2ZW4gbnVtYmVyLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==