令狐沖去少林寺觀光，少林寺有四種代幣，面額分別是[1, 5, 10, 50]，令狐沖拿了 n 元去換代幣， 請問以這四種代幣湊成 n 元，最少要多少枚代幣？

輸入格式

第一行是一個正整數 m，代表有幾筆測資， 以下有 m 行，每行是一筆測資， 每筆測資是一個正整數 n，n<1000。

輸出格式

依序每一行輸出每一筆測資的最少的代幣數量。

範例輸入

3
21
50
123

範例輸出

3
1
7

說明:\(21 = 10*2 + 1, 50 = 50*1, 123 = 50*2 + 1*3\)