Ayush and Coins

5

4 votes
Easy
Problem

Ayush has infinite number of coins of the denominations of 1, 4 and 5. (Rich Dude)

So, he always keeps buying things. But as he is smart, he wants to carry minimum number of coins while going out shopping. He knows the price of all the stuffs he will be buying from different shops.

You need to find the minimum number of coins Ayush has to spend in each of the Shops.

INPUT:

The first line of input consists of a single integer T denoting number of shops Ayush visits.

Each of the next T lines consists of a single integer Ai denoting the amount payable at that shop.

OUTPUT:

For each test case, print a single integer Cmin denoting minimum number of coins Ayush spends at that shop.

CONSTRAINTS:

1 ≤ T ≤ 105

0 ≤ Ai ≤ 1018

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

In each of the first three shops he spends one coin of value 1, 4 and 5 respectively.

In fourth shop he spends two coins of values 1 and 5.

In fifth shop he spends two coins both of values 4.

All the participants need to register on the given link:goo.gl/MDh9FR

Editor Image

?