동전 문제

구사과국에서는 동전만 사용한다. 동전의 가치는 다음과 같다.

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

즉, 모든 정수 K >= 0에 대해 가치가 10^K인 동전과 25 x 100^K인 동전이 있다.

구사과국에 사는 구사과는 초콜릿을 하나 사려고 한다. 초콜릿의 가격이 주어졌을 때, 정확히 그 가격만큼 지불하는 데 필요한 동전 개수의 최솟값을 구하라. 각 동전은 무한히 많이 사용할 수 있다.

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

각 테스트 케이스마다 필요한 동전 개수의 최솟값을 한 줄에 하나씩 출력한다.