Coin Problem

Time limit2sMemory limit128 MB

Summary

Find the minimum number of coins from denominations 10^K and 25x100^K needed to make an exact price up to 10^15.

Level: Medium7 of 10
Topics: Greedy, Math, Number theory, Dynamic programming
Solved: No attempts yet

Problem

In the country of Gusagwa, only coins are used. The coin values are as follows.

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

Equivalently, for every integer K >= 0, there is a coin worth 10^K and a coin worth 25 x 100^K.

Gusagwa wants to buy one chocolate. Given the price of the chocolate, find the minimum number of coins needed to pay exactly that price. There are infinitely many coins of each value.

Input

The first line contains the number of test cases T. Each of the next T lines contains one chocolate price. Each price is a positive integer not greater than 10^15.

Output

For each test case, output the minimum number of coins needed on its own line.

Examples2

Example 1
Input
```
2
47
9
```
Expected output
```
5
9
```
Example 2
Input
```
2
250111
76540123
```
Expected output
```
4
16
```