在 Berland,通常使用价值 $$$1$$$、$$$3$$$ 和 $$$5$$$ burles 的硬币(burles 是当地货币)。
伊娃必须在商店里准确支付$$$n$$$ burles。她拥有无限数量的所有三种类型的硬币。然而,她不喜欢用价值 $$$1$$$ burle 的硬币支付——她认为它们使用起来最方便。
帮助伊娃计算她必须使用的价值 $$$1$$$ burle 的最小硬币数量,如果她必须支付恰好 $$$n$$$ burle。请注意,她可以花费任意数量的价值 $$$3$$$ 和/或 $$$5$$$ burles 的硬币。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。
每个测试用例由一行组成,包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$)。
输出
对于每个测试用例,打印一个整数 — Eva 必须使用的 $$$1$$$-burle 硬币的最小数量。
示例
输入 #1
5 7 8 42 2 11
输出 #1
1 0 0 2 0
注意
在第一个测试用例中,Eva 应该使用价值 $$$1$$$ burle 的 $$$1$$$ 硬币,以及价值 $$$3$$$ burle 的 $$$2$$$ 硬币。
在第二个测试用例中,Eva 应该使用价值 $$$3$$$ burles 的 $$$1$$$ 硬币和价值 $$$5$$$ burles 的 $$$1$$$ 硬币。
在第三个测试用例中,Eva 应该使用价值 $$$3$$$ burles 的 $$$14$$$ 硬币。
在第四个测试用例中,Eva 应该使用价值 $$$1$$$ burle 的 $$$2$$$ 硬币。
在第五个测试用例中,Eva 应该使用价值 $$$3$$$ burles 的 $$$2$$$ 硬币和价值 $$$5$$$ burles 的 $$$1$$$ 硬币。