PKU 3085. Quick Change

재빠른 거스름돈 주기

Time Limit: 1000MS	Memory Limit: 65536K
Total Submissions: 3979	Accepted: 2914

설명

J.P. Flathead의 가게에서 계산을 할 싼 인력을 고용했습니다. 보통 고등학생들을 고용하는데, 이 알바들은 손님들에게 거스름돈을 줄 때 실수가 많습니다. Flathead는 자기가 직접 계산을 해서 거스름돈을 줄 때 실수하는 금액보다, 알바들이 손님들에게 거스름돈을 줄 때 실수하는 금액이 더 많다는 것을 알게 되었습니다.

Flathead는 당신이 손님들에게 줄 거스름돈에 들어가는 quarter($0.25), dime($0.10), nickel($0.05), penny($0.01) 4개의 동전들이 각각 몇개씩인지를 계산하는 프로그램을 만들었으면 합니다. Flathead는 거스름돈으로 줄 금액이 $5.00 를 넘지 않고 최소한의 동전들로 거스름돈을 주기를 바랍니다. 예를 들어 거스름돈이 $1.24 라면, 손님에게 줄 거스름돈은 4개의 quarter, 2개의 dime, 니켈은 없고 4개의 penny가 되어야 합니다.

입력

첫번째 줄에 입력할 것은 정수 N인데 이 숫자는 계산할 데이터셋의 개수를 의미합니다. 각 데이터셋에는 거스름돈으로 계산할 하나의 정수 C(1 ≤ C ≤ 500)를 입력합니다.

출력

각 데이터셋에 대해서 알맞은 숫자와 공백, 그리고 동전의 단위를 나타내는 문자열을 출력합니다:

Q QUARTER(S), D DIME(S), n NICKEL(S), P PENNY(S)

Q는 quarter의 수량을, D는 dime의 수량을, n은 nickel의 수량을, 그리고 P는 penny의 수량을 나타냅니다.

입력 예시

3
124
25
194

출력 예시

1 4 QUARTER(S), 2 DIME(S), 0 NICKEL(S), 4 PENNY(S)
2 1 QUARTER(S), 0 DIME(S), 0 NICKEL(S), 0 PENNY(S)
3 7 QUARTER(S), 1 DIME(S), 1 NICKEL(S), 4 PENNY(S)

Source

Greater New York 2006