在贝兰，常见的硬币面值$1$、金$3$和$5$布尔（布尔是当地货币）。

伊娃在商店里得付$n$个牛皮饼。她拥有无限数量的三种硬币。不过，她不喜欢用价值$1$burle的硬币支付——她认为那样使用起来最方便。

帮伊娃计算如果必须支付正好$n$$1$个伯勒，她必须用多少币值。注意她可以花费任何价值$3$和/或$5$burles的硬币。

输入

第一行包含一个整数$t$（$1 \le t \le 100$）——测试用例的数量。

每个测试用例由一行组成，包含一个整数$n$（$1 \le n \le 100$）。

输出

每个测试用例打印一个整数——这是伊娃必须使用的最少数量$1$布勒硬币。

注释

在第一个测试案例中，伊娃应使用价值$1$$1$枚硬币，$2$以及价值$3$枚硬币。

在第二个测试场景中，伊娃应使用价值$3$枚$1$枚硬币和$1$$5$枚硬币。

第三个测试场景中，EVA应使用价值$3$布尔的$14$枚硬币。

在第四个测试场景中，伊娃应使用价值$1$布尔的$2$枚硬币。

在第五个测试中，伊娃应使用价值$3$ burles的$2$枚硬币和$5$枚$1$枚硬币。

样例

5
7
8
42
2
11

1
0
0
2
0