Coin 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.

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.

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