시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 422 62 51 19.392%

문제

김형택이 세운 나라의 화폐 체계는 단순하다. 이곳은 동전만 사용하고, 동전은 다음과 같이 다른 값을 가진다.

1, 10, 25, 100, 1000, 2500, 10000, 100000, ...

식으로 나타내면 0보다 크거나 같은 모든 K에 대해서 10^K인 동전과 25*100^K인 동전이 있다.

이기훈은 이 나라에서 새로운 차를 한 대 사려고 한다. 이기훈은 차를 살 때, 가능하면 동전의 개수를 최소로 하려고 한다. 이기훈이 필요한 동전 개수의 최솟값을 출력하는 프로그램을 작성하시오. (모든 값의 동전의 개수는 무한하고, 차를 살 때 정확하게 차의 값만큼 지불해야 한다.)

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 차의 값이 주어진다. 이 값은 10^15보다 작거나 같은 자연수이다.

출력

총 T개의 줄에 각각의 테스트 케이스의 필요한 동전의 개수를 출력한다.

예제 입력

2
47
9

예제 출력

5
9

힌트

출처