Có lẽ bạn không biết (tại chúng tôi chưa kể), Loli có một người bạn thân. Không ai biết chắc chắn mối quan hệ giữa hai người, là tình bạn hay tình yêu hay trên tình bạn dưới tình yêu, người đó chính là Lilo. Lilo là một tay chơi có tiếng trong vùng với acc Genshin Impact lv69 và acc LOL full skin tướng (do đã nạp sương sương gần 9tr RP mà không ghê tay). Khi sang thế giới khác, vì là whale chúa tể nên hắn ta thường xuyên bao Loli tiền đồ ăn. Anh ta dẫn bạn đi đến một quán ăn nổi tiếng dành cho rich kid. Đồ ăn trong quán rất phong phú, có thể kể đến như thịt gà luộc với bò húc hay thịt bò ướp vàng 69K. Thế nhưng Lilo lại quyết định bao Loli một đĩa rau muống luộc.

Vì nhà có điều kiện nên Lilo chỉ dùng những đồng tiền to vjp pr0. Hắn ta muốn đổi những tờ giấy vụn ấy thành những tờ giấy có giá trị nhỏ hơn để trả tiền cho hợp pháp. Vì lý do tất yếu, thế giới mà bọn họ đang ở không phải là Trái Đất mà là Tân Thế giới. Những đồng tiền mà họ dùng ở đó có mệnh giá lần lượt là 1đ, 5đ, 10đ, 50đ. Bạn hãy lập ra một thuật toán để tìm số tờ tiền ít nhất mà Lilo cần phải đổi thành để có thể sử dụng tiền một cách hợp pháp.

Input:

• Dòng đầu tiên chứa một số nguyên ~T~ ~(1 \le T \le 10^5)~ thể hiện số truy vấn cần thực hiện.
• ~T~ dòng tiếp theo, mỗi dòng bao gồm một số nguyên ~N~ duy nhất ~(1 ≤ N ≤ 10^{18})~ — thể hiện số tiền mà Lilo cần phải đổi. Đảm bảo input luôn cho kết quả.

Output:

• Gồm ~T~ dòng, in ra trên mỗi dòng số tờ tiền cần phải đổi thành ít nhất có thể.

Sample Input

3
12
9
3

Sample Output

3
5
3