三种票币

题目描述

票币面额为1、3、4，每种可用无限张。总面额必须恰好为X，求最少使用张数。X=0时可以不用票币。每条输出最少张数。

输入格式

第一行输入查询数T；接下来T行，每行输入X。

输出格式

每次查询输出一行，按输入顺序回答。

样例 1

输入

2
6
0

输出

2
0

说明

6可用两张3；0无需票币。

样例 2

输入

1
10

输出

3

说明

4+3+3共3张。

数据范围

• 1 ≤ T ≤ 20
• 第1个参数在[0,1000]内，为整数。