세탁소 사장 동혁

import sys


def main():
    input = sys.stdin.readline

    for _ in range(int(input())):
        n = int(input())

        quarter, n = divmod(n, 25)
        dime, n = divmod(n, 10)
        nickel, n = divmod(n, 5)
        penny = n

        print(quarter, dime, nickel, penny)


main()

각 동전을 그보다 액수가 작은 동전으로 대체하면 항상 동전의 수가 많아짐을 관찰할 수 있습니다. 따라서 가능하면 액수가 큰 동전을 많이 사용해야하고, 이때 그 동전의 개수는 남은 액수를 그 동전의 액수로 나눈 몫이 됩니다. 나머지 금액은 다음으로 액수가 큰 동전으로 내고, 이 과정을 반복하면 해결할 수 있습니다. 앞에서 살펴본 divmod 함수를 이용하면 이를 간단하게 구현할 수 있습니다.