Розглянемо валютну систему, в якій є купюри шести номіналів:1, 2, 5, 10, 50, 100.

Зайдіть найменшу кількість купюр щоб набрати суму \(N\).

Формат вхідних даних

Перший рядок містить ціле число T, загальну кількість тестів.

Потім слідують T рядків, кожен рядок містить ціле число N.

Формат вихідних даних

У вихідний потік вивести, в окремих рядках для кожного тесту, відповідь на поставлене завдання

Обмеження

• 1 ≤ T ≤ 1000

• 1 ≤ N ≤ 1000000

Приклад вхідних даних

3
1200
500
242

Приклад вихідних даних

12
5
7