Problem description

Kolejne zadanie o wydawanie reszty. No nie! Znowu?

Dana jest kwota K (reszta), którą chcemy przedstawić w postaci sumy jak najmniejszej liczby składników. Każdy składnik musi należeć do zadanego zbioru (nominałów). A zbiór nominałów składa się z nominałów 10ⁿ oraz 25 ⋅ 10²ⁿ, dla dowolnego nieujemnego całkowitego n. Zatem zbiór nominałów jest następujący: {1, 10, 25, 100, 1 000, 2 500, 10 000, 100 000, 250 000, …}.

Napisz program, który: wczyta wiele kwot do wydania, wyznaczy dla każdej z nich minimalną liczbę nominałów, niezbędnych do wydania tej kwoty i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, określająca liczbę zestawów danych. W kolejnych wierszach znajdują się kolejne zestawy danych.

Opis każdego zestawu danych składa się z jednej liczby naturalnej K_i, określającej kwotę do wydania.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym wierszu powinna się znaleźć odpowiedź dla i-tego zestawu danych. Odpowiedź dla każdego z zestawów danych to jedna liczba całkowita – minimalna liczba nominałów niezbędna do wydania kwoty K_i.

Ograniczenia

1 ≤ Q ≤ 100 000, 1 ≤ K_i ≤ 10¹⁷.

Przykład

3
26
21
179

2
3
8