严神的算法功底突然变差，连dp也不会了。
这一次， 他拿着一堆硬币去买东西。 他持有4种硬币，面值分别为1、4、16、64元。 他想买一件价值为 n 的物品， 请问他至少需要多少枚硬币？
输入包括多组数据。
第一行为数字 T ，含义为前文所述。
接下来 T 行， 每行一个整数 n ，代表物品的价值。
针对每组输入， 输出一行一个整数，最少需要的硬币数。
3 10 100 1000
4 4 19
对于 100\% 的数据， 1≤ T ≤10, 0 ≤ N < 2^{31} .