시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 2746 1906 1725 70.988%

문제

꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보나치를 만들었다. 꿍만의 피보나치 함수가 koong(n)이라고 할 때,

n < 2 :                         1
n = 2 :                         2
n = 3 :                         4
n > 3 : koong(n − 1) + koong(n − 2) + koong(n − 3) + koong(n − 4)

이다.

여러분도 꿍 피보나치를 구해보아라.

 

입력

입력의 첫번째 줄을 테스트케이스의 개수 t (0 < t < 69)가 주어진다. 다음 t줄에는 몇번째 피보나치를 구해야하는지를 나타내는 n(0 ≤ n ≤ 67)이 주어진다.

출력

각 테스트케이스에 대해, 각 줄에 꿍 피보나치값을 출력하라.

예제 입력 1

8
0
1
2
3
4
5
30
67

예제 출력 1

1
1
2
4
8
15
201061985
7057305768232953720
W3sicHJvYmxlbV9pZCI6Ijk1MDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJHZW5lcmF0aW9ucyBvZiBUcmliYmxlcyIsImRlc2NyaXB0aW9uIjoiPHA+XHVhZmNkXHVjNzQwIFx1YWQ3MFx1YjMwMFx1YzVkMFx1YzExYyBcdWM5YzRcdWM5ZGMgXHVkNTYwXHVjOWQzXHVjNzc0IFx1YzVjNlx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YWZjZFx1YjljY1x1Yzc1OCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNThcdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0XHViY2Y0XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZTMwXHVjODc0XHVjNzU4IFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OFx1YjI5NCBcdWIxMDhcdWJiMzQgXHViMmU4XHVjMjFjXHVkNTc0XHVjMTFjIFx1YWZjZFx1Yzc0MCBcdWM4ODBcdWIzNTQgXHViY2Y1XHVjN2ExXHVkNTVjIFx1ZDUzY1x1YmNmNFx1YjA5OFx1Y2U1OFx1Yjk3YyBcdWI5Y2NcdWI0ZTRcdWM1YjRcdWJjZjRcdWFjZTBcdWM3OTAgXHVkNTVjXHViMmU0LiBcdWFkZjhcdWI3OThcdWMxMWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWQ1M2NcdWJjZjRcdWIwOThcdWNlNThcdWI5N2MgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWFmY2RcdWI5Y2NcdWM3NTggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4IFx1ZDU2OFx1YzIxOFx1YWMwMCBrb29uZyhuKVx1Yzc3NFx1Yjc3Y1x1YWNlMCBcdWQ1NjAgXHViNTRjLDxcL3A+XHJcblxyXG48cHJlPlxyXG5uICZsdDsgMiA6ICAgICAgICAgICAgICAgICAgICAgICAgIDFcclxubiA9IDIgOiAgICAgICAgICAgICAgICAgICAgICAgICAyXHJcbm4gPSAzIDogICAgICAgICAgICAgICAgICAgICAgICAgNFxyXG5uICZndDsgMyA6IGtvb25nKG4gJm1pbnVzOyAxKSArIGtvb25nKG4gJm1pbnVzOyAyKSArIGtvb25nKG4gJm1pbnVzOyAzKSArIGtvb25nKG4gJm1pbnVzOyA0KVxyXG48XC9wcmU+XHJcblxyXG48cD5cdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YjdlY1x1YmQ4NFx1YjNjNCBcdWFmY2QgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YmNmNFx1YzU0NFx1Yjc3Yy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NTggXHVjY2FiXHViYzg4XHVjOWY4IFx1YzkwNFx1Yzc0NCBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IHQmbmJzcDsoMCAmbHQ7IHQgJmx0OyA2OSlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgdFx1YzkwNFx1YzVkMFx1YjI5NCBcdWJhODdcdWJjODhcdWM5ZjggXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4XHViOTdjIFx1YWQ2Y1x1ZDU3NFx1YzU3Y1x1ZDU1OFx1YjI5NFx1YzljMFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgbigwICZsZTsgbiAmbGU7IDY3KVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzQsIFx1YWMwMSBcdWM5MDRcdWM1ZDAmbmJzcDtcdWFmY2QgXHVkNTNjXHViY2Y0XHViMDk4XHVjZTU4XHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1Yjc3Yy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI5NTA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiR2VuZXJhdGlvbnMgb2YgVHJpYmJsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlRyaWJibGVzIGFyZSB0aGUgY3V0ZSwgZnV6enksIGN1ZGRseSBhbmltYWxzIHRoYXQgaGF2ZSB2b3JhY2lvdXMgYXBwZXRpdGVzIGFuZCByZXByb2R1Y3Rpb24gcmF0ZXMgdGhhdCByaXZhbCBhbnkgY29tcGxleCBvcmdhbmlzbSBpbiB0aGUgZ2FsYXh5ICh0cmliYmxlcyBhcmUgYm9ybiBwcmVnbmFudCEpLiBBZnRlciBiZWluZyBpbnRyb2R1Y2VkIHRvIHRoZSBFbnRlcnByaXNlIGFuZCBpdHMgY3JldywgaXQgd2FzIHF1aWNrbHkgZGlzY292ZXJlZCB3aGF0IGEgbnVpc2FuY2UgdHJpYmJsZXMgY291bGQgYmUuIEluIGEgdmVyeSBzaG9ydCBhbW91bnQgb2YgdGltZSwgdHJpYmJsZXMgd2VyZSBldmVyeXdoZXJlIG9uIHRoZSBzaGlwLjxcL3A+XHJcblxyXG48cD5Gb3J0dW5hdGVseSBmb3IgdGhlIEVudGVycHJpc2UsIEVuZ2luZWVyIFNjb3R0IHdhcyBhYmxlIHRvIHRyYW5zcG9ydCB0aGVtIHRvIGEgbmVhcmJ5IEtsaW5nb24gdmVzc2VsLiBUaGUgS2xpbmdvbnMgd2VyZSB1bmF3YXJlIG9mIHRoZSBpc3N1ZXMgdHJpYmJsZXMgY291bGQgY2F1c2UgYW5kIGJyb3VnaHQgdGhlbSBpbnRvIEtsaW5nb24gc3BhY2UsIHdoZXJlIHRoZSB0cmliYmxlcyBzcHJlYWQgbGlrZSBsb2N1c3RzIGFuZCBkZXZhc3RhdGVkIGVjb3N5c3RlbXMgb2YgcGxhbmV0cyBhY3Jvc3MgdGhlIEtsaW5nb24gRW1waXJlLjxcL3A+XHJcblxyXG48cD5NZW1iZXJzIG9mIHRoZSBVbml0ZWQgRmVkZXJhdGlvbnMgb2YgUGxhbmV0cyAoVGhlIEZlZGVyYXRpb24pIGZvdW5kIHRoaXMgZXh0cmVtZWx5IGFtdXNpbmcgYW5kIHVzZWQgdGhlIGNhbGN1bGF0aW9uIG9mIHRyaWJibGUgcmVwcm9kdWN0aW9uIGFzIGFuIGFjYWRlbWljIGV4ZXJjaXNlIGZvciBmaXJzdCB5ZWFyIHN0dWRlbnRzIGF0IGl0cyBhY2FkZW15LjxcL3A+XHJcblxyXG48cD5UaGUgZm9sbG93aW5nIHNlcXVlbmNlIG9mIG51bWJlcnMgcmVwcmVzZW50cyBob3cgdHJpYmJsZXMgcmVwcm9kdWNlLiBUaGUgZmlyc3QgbnVtYmVyIHJlcHJlc2VudHMgZ2VuZXJhdGlvbiAwLCB0aGUgc2Vjb25kIGdlbmVyYXRpb24gMSwgYW5kIHNvIG9uLjxcL3A+XHJcblxyXG48cD4xLCAxLCAyLCA0LCA4LCAxNSwgMjksIDU2PFwvcD5cclxuXHJcbjxwPlRoZSBmb2xsb3dpbmcgcmVjdXJyZW5jZSBjYW4gYmUgdXNlZCB0byByZXByZXNlbnQgdGhlIGFib3ZlIHNlcXVlbmNlLCB3aGVyZSBuIHJlcHJlc2VudHMgdGhlIGdlbmVyYXRpb24gbnVtYmVyOiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG5uICZsdDsgMiA6ICAgICAgICAgICAgICAgICAgICAgICAgIDFcclxubiA9IDIgOiAgICAgICAgICAgICAgICAgICAgICAgICAyXHJcbm4gPSAzIDogICAgICAgICAgICAgICAgICAgICAgICAgNFxyXG5uICZndDsgMyA6IGdlbihuICZtaW51czsgMSkgKyBnZW4obiAmbWludXM7IDIpICsgZ2VuKG4gJm1pbnVzOyAzKSArIGdlbihuICZtaW51czsgNClcclxuPFwvcHJlPlxyXG5cclxuPHA+VGhvc2UgYXQgdGhlIGFjYWRlbXkgdGhhdCBrbm93IHNvbWV0aGluZyBhYm91dCBvbGQgRWFydGggaGlzdG9yeSBoYXZlIGpva2luZ2x5IGNhbGxlZCB0aGUgcmVjdXJyZW5jZSAmbHNxdW87VHJpYmJsZW5hY2NpJnJzcXVvOy48XC9wPlxyXG5cclxuPHA+WW91ciBqb2IgYXMgYSBmaXJzdCB5ZWFyIHN0dWRlbnQgYXQgdGhlIGFjYWRlbXkgaXMgdG8gYWNjdXJhdGVseSBhbmQgcmFwaWRseSBjYWxjdWxhdGUgaG93IG1hbnkgdHJpYmJsZXMgdGhlcmUgd2lsbCBiZSBmb3IgYSBnaXZlbiAmbHNxdW87VHJpYmJsZW5hY2NpJnJzcXVvOyBudW1iZXIuIFRoZSBmYWN0IGlzLCBldmFsdWF0aW5nIHRoZSBhYm92ZSByZWN1cnJlbmNlIHJlY3Vyc2l2ZWx5IGlzIHNsb3dlciB0aGFuIGNoZW1pY2FsIHByb3B1bHNpb24gZm9yIGludGVyc3RlbGxhciB0cmF2ZWwhIFRvIGRvIHNvIGZvciBtb3JlIHRoYW4gYSBoYW5kZnVsIG9mIGdlbmVyYXRpb25zIHdvdWxkIGNsZWFybHkgYmUgaWxsb2dpY2FsLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgd2lsbCBiZSBhbiBpbnRlZ2VyIHQgKDAgJmx0OyB0ICZsdDsgNjkpIHJlcHJlc2VudGluZyB0aGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMuIEZvbGxvd2luZyB0aGlzIHdpbGwgYmUgdCBpbnRlZ2VyIHZhbHVlcywgb25lIHBlciBsaW5lLiBFYWNoIG9mIHRoZXNlIHdpbGwgcmVwcmVzZW50IGEgZ2VuZXJhdGlvbiBudW1iZXIgZyAoMCAmbGU7IGcgJmxlOyA2NykgdG8gY2FsY3VsYXRlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGdlbmVyYXRpb24gbnVtYmVyIHJlYWQsIGRpc3BsYXkgdGhlIGNvcnJlc3BvbmRpbmcgJmxzcXVvO1RyaWJibGVuYWNjaSZyc3F1bzsgdmFsdWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d