시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3880100575727.729%

문제

구사과국은 동전만 사용하고, 동전의 가치는 다음과 같다.

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

즉, 식으로 표현하면 K ≥ 0를 만족하는 모든 K에 대해서, 가치가 10K인 동전과 25×100K인 동전이 있는 것이다.

구사과국에 살고 있는 구사과는 초콜릿을 하나 구매해 5차원 세계로 이사가려고 한다. 초콜릿의 가격이 주어졌을때, 이를 구매하기 위해 필요한 동전 개수의 최솟값을 구해보자. 각 동전의 개수는 무한하고, 구매할 때는 정확하게 초콜릿의 가격만큼만 지불해야 한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다.

출력

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

예제 입력 1

2
47
9

예제 출력 1

5
9

예제 입력 2

2
250111
76540123

예제 출력 2

4
16

출처