시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1041 860 788 85.005%

문제

미국으로 유학간 동혁이는 세탁소를 운영하고 있다. 동혁이는 최근에 아르바이트로 고등학생 리암을 채용했다.

동혁이는 리암에게 실망했다.

리암은 거스름돈을 주는 것을 자꾸 실수한다.

심지어 \$0.5달러를 줘야하는 경우에 거스름돈으로 \$5달러를 주는것이다!

어쩔수 없이 뛰어난 코딩 실력을 발휘해 리암을 도와주는 프로그램을 작성하려고 하지만, 디아블로를 하느라 코딩할 시간이 없어서 이 문제를 읽고 있는 여러분이 대신 해주어야 한다.

거스름돈의 액수가 주어지면 리암이 줘야할 쿼터(Quarter, \$0.25)의 개수, 다임(Dime, \$0.10)의 개수, 니켈(Nickel, \$0.05)의 개수, 페니(Penny, \$0.01)의 개수를 구하는 프로그램을 작성하시오. 거스름돈은 항상 \$5.00 이하이고, 손님이 받는 동전의 개수를 최소로 하려고 한다. 예를 들어, \$1.24를 거슬러 주어야 한다면, 손님은 4쿼터, 2다임, 0니켈, 4페니를 받게 된다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 거스름돈 C를 나타내는 정수 하나로 이루어져 있다. C의 단위는 센트이다. (1달러 = 100센트) (1<=C<=500)

출력

각 테스트케이스에 대해 필요한 쿼터의 개수, 다임의 개수, 니켈의 개수, 페니의 개수를 공백으로 구분하여 출력한다.

예제 입력 1

3
124
25
194

예제 출력 1

4 2 0 4
1 0 0 0
7 1 1 4

힌트

W3sicHJvYmxlbV9pZCI6IjI3MjAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxMzhcdWQwYzFcdWMxOGMgXHVjMGFjXHVjN2E1IFx1YjNkOVx1ZDYwMSIsImRlc2NyaXB0aW9uIjoiPHA+XHViYmY4XHVhZDZkXHVjNzNjXHViODVjIFx1YzcyMFx1ZDU1OVx1YWMwNCBcdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHVjMTM4XHVkMGMxXHVjMThjXHViOTdjIFx1YzZiNFx1YzYwMVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YjNkOVx1ZDYwMVx1Yzc3NFx1YjI5NCBcdWNkNWNcdWFkZmNcdWM1ZDAgXHVjNTQ0XHViOTc0XHViYzE0XHVjNzc0XHVkMmI4XHViODVjIFx1YWNlMFx1YjRmMVx1ZDU1OVx1YzBkZCBcdWI5YWNcdWM1NTRcdWM3NDQgXHVjYzQ0XHVjNmE5XHVkNTg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzZDlcdWQ2MDFcdWM3NzRcdWIyOTQgXHViOWFjXHVjNTU0XHVjNWQwXHVhYzhjIFx1YzJlNFx1YjlkZFx1ZDU4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWFjXHVjNTU0XHVjNzQwIFx1YWM3MFx1YzJhNFx1Yjk4NFx1YjNjOFx1Yzc0NCBcdWM4ZmNcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1Yzc5MFx1YWZiOCBcdWMyZTRcdWMyMThcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzJlY1x1YzljMFx1YzViNCBcXCQwLjVcdWIyZWNcdWI3ZWNcdWI5N2MgXHVjOTE4XHVjNTdjXHVkNTU4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWFjNzBcdWMyYTRcdWI5ODRcdWIzYzhcdWM3M2NcdWI4NWMgXFwkNVx1YjJlY1x1YjdlY1x1Yjk3YyBcdWM4ZmNcdWIyOTRcdWFjODNcdWM3NzRcdWIyZTQhPFwvcD5cclxuXHJcbjxwPlx1YzViNFx1Y2E1NFx1YzIxOCBcdWM1YzZcdWM3NzQgXHViNmYwXHVjNWI0XHViMDljIFx1Y2Y1NFx1YjUyOSBcdWMyZTRcdWI4MjVcdWM3NDQgXHViYzFjXHVkNzE4XHVkNTc0IFx1YjlhY1x1YzU1NFx1Yzc0NCBcdWIzYzRcdWM2NDBcdWM4ZmNcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NThcdWM5YzBcdWI5Y2MsIFx1YjUxNFx1YzU0NFx1YmUxNFx1Yjg1Y1x1Yjk3YyBcdWQ1NThcdWIyOTBcdWI3N2MgXHVjZjU0XHViNTI5XHVkNTYwIFx1YzJkY1x1YWMwNFx1Yzc3NCBcdWM1YzZcdWM1YjRcdWMxMWMgXHVjNzc0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWM3N2RcdWFjZTAgXHVjNzg4XHViMjk0IFx1YzVlY1x1YjdlY1x1YmQ4NFx1Yzc3NCBcdWIzMDBcdWMyZTAgXHVkNTc0XHVjOGZjXHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzcwXHVjMmE0XHViOTg0XHViM2M4XHVjNzU4IFx1YzU2MVx1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzQgXHViOWFjXHVjNTU0XHVjNzc0IFx1YzkxOFx1YzU3Y1x1ZDU2MCBcdWNmZmNcdWQxMzAoUXVhcnRlciwgXFwkMC4yNSlcdWM3NTggXHVhYzFjXHVjMjE4LCBcdWIyZTRcdWM3ODQoRGltZSwgXFwkMC4xMClcdWM3NTggXHVhYzFjXHVjMjE4LCBcdWIyYzhcdWNmMDgoTmlja2VsLCBcXCQwLjA1KVx1Yzc1OCBcdWFjMWNcdWMyMTgsIFx1ZDM5OFx1YjJjOChQZW5ueSwgXFwkMC4wMSlcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWFjNzBcdWMyYTRcdWI5ODRcdWIzYzhcdWM3NDAgXHVkNTZkXHVjMGMxIFxcJDUuMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHVhY2UwLCBcdWMxOTBcdWIyZDhcdWM3NzQgXHViYzFiXHViMjk0IFx1YjNkOVx1YzgwNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDVjXHVjMThjXHViODVjIFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzYwOFx1Yjk3YyBcdWI0ZTRcdWM1YjQsIFxcJDEuMjRcdWI5N2MgXHVhYzcwXHVjMmFjXHViN2VjIFx1YzhmY1x1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTRcdWJhNzQsIFx1YzE5MFx1YjJkOFx1Yzc0MCA0XHVjZmZjXHVkMTMwLCAyXHViMmU0XHVjNzg0LCAwXHViMmM4XHVjZjA4LCA0XHVkMzk4XHViMmM4XHViOTdjIFx1YmMxYlx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWFjNzBcdWMyYTRcdWI5ODRcdWIzYzggQ1x1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBDXHVjNzU4IFx1YjJlOFx1YzcwNFx1YjI5NCBcdWMxM2NcdWQyYjhcdWM3NzRcdWIyZTQuICgxXHViMmVjXHViN2VjID0gMTAwXHVjMTNjXHVkMmI4KSAoMSZsdDs9QyZsdDs9NTAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjhcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0IFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNmZmNcdWQxMzBcdWM3NTggXHVhYzFjXHVjMjE4LCBcdWIyZTRcdWM3ODRcdWM3NTggXHVhYzFjXHVjMjE4LCBcdWIyYzhcdWNmMDhcdWM3NTggXHVhYzFjXHVjMjE4LCBcdWQzOThcdWIyYzhcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1YWNmNVx1YmMzMVx1YzczY1x1Yjg1YyBcdWFkNmNcdWJkODRcdWQ1NThcdWM1ZWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD48aWZyYW1lIGZyYW1lYm9yZGVyPVwiMFwiIGhlaWdodD1cIjQ4MFwiIHNyYz1cImh0dHBzOlwvXC93d3cueW91dHViZS5jb21cL2VtYmVkXC81S19jZnJYMWxyc1wiIHdpZHRoPVwiODUzXCI+PFwvaWZyYW1lPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjcyMCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlF1aWNrIENoYW5nZSIsImRlc2NyaXB0aW9uIjoiPHA+Si5QLiBGbGF0aGVhZCZyc3F1bztzIEdyb2NlcnkgU3RvcmUgaGlyZXMgY2hlYXAgbGFib3IgdG8gbWFuIHRoZSBjaGVja291dCBzdGF0aW9ucy4gVGhlIHBlb3BsZSBoZSBoaXJlcyAodXN1YWxseSBoaWdoIHNjaG9vbCBraWRzKSBvZnRlbiBtYWtlIG1pc3Rha2VzIG1ha2luZyBjaGFuZ2UgZm9yIHRoZSBjdXN0b21lcnMuIEZsYXRoZWFkLCB3aG8mcnNxdW87cyBhIGJpdCBvZiBhIHRpZ2h0d2FkLCBmaWd1cmVzIGhlIGxvc2VzIG1vcmUgbW9uZXkgZnJvbSB0aGVzZSBtaXN0YWtlcyB0aGFuIGhlIG1ha2VzOyB0aGF0IGlzLCB0aGUgZW1wbG95ZWVzIHRlbmQgdG8gZ2l2ZSBtb3JlIGNoYW5nZSB0byB0aGUgY3VzdG9tZXJzIHRoYW4gdGhleSBzaG91bGQgZ2V0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5GbGF0aGVhZCB3YW50cyB5b3UgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbnVtYmVyIG9mIHF1YXJ0ZXJzIChcXCQwLjI1KSwgZGltZXMgKFxcJDAuMTApLCBuaWNrZWxzIChcXCQwLjA1KSBhbmQgcGVubmllcyAoXFwkMC4wMSkgdGhhdCB0aGUgY3VzdG9tZXIgc2hvdWxkIGdldCBiYWNrLiBGbGF0aGVhZCBhbHdheXMgd2FudHMgdG8gZ2l2ZSB0aGUgY3VzdG9tZXImcnNxdW87cyBjaGFuZ2UgaW4gY29pbnMgaWYgdGhlIGFtb3VudCBkdWUgYmFjayBpcyBcXCQ1LjAwIG9yIHVuZGVyLiBIZSBhbHNvIHdhbnRzIHRvIGdpdmUgdGhlIGN1c3RvbWVycyBiYWNrIHRoZSBzbWFsbGVzdCB0b3RhbCBudW1iZXIgb2YgY29pbnMuIEZvciBleGFtcGxlLCBpZiB0aGUgY2hhbmdlIGR1ZSBiYWNrIGlzIFxcJDEuMjQsIHRoZSBjdXN0b21lciBzaG91bGQgcmVjZWl2ZSA0IHF1YXJ0ZXJzLCAyIGRpbWVzLCAwIG5pY2tlbHMsIGFuZCA0IHBlbm5pZXMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhbiBpbnRlZ2VyIE4gd2hpY2ggaXMgdGhlIG51bWJlciBvZiBkYXRhc2V0cyB0aGF0IGZvbGxvdy4gRWFjaCBkYXRhc2V0IGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBhIHNpbmdsZSBpbnRlZ2VyIHdoaWNoIGlzIHRoZSBjaGFuZ2UgZHVlIGluIGNlbnRzLCBDLCAoMSAmbGU7IEMgJmxlOyA1MDApLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGFzZXQsIHByaW50IG91dCB0aGUgZGF0YXNldCBudW1iZXIsIGEgc3BhY2UsIGFuZCB0aGUgc3RyaW5nOiZuYnNwOzxcL3A+XHJcblxyXG48cHJlPlxyXG5RIFFVQVJURVIoUyksIEQgRElNRShTKSwgbiBOSUNLRUwoUyksIFAgUEVOTlkoUykmbmJzcDs8XC9wcmU+XHJcblxyXG48cD5XaGVyZSBRIGlzIGhlIG51bWJlciBvZiBxdWFydGVycywgRCBpcyB0aGUgbnVtYmVyIG9mIGRpbWVzLCBuIGlzIHRoZSBudW1iZXIgb2Ygbmlja2VscyBhbmQgUCBpcyB0aGUgbnVtYmVyIG9mIHBlbm5pZXMuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d