题目描述

徐老师最近很空，于是他别出心裁，想了一个集合游戏。

首先，徐老师有一个集合 $A = \{1, 2, 3, \ldots, n\}$ 和一个空集合 $B$。他将把集合 $A$ 中的一些元素放入集合 $B$ 中。

由于徐老师不喜欢数字 $5$ 和 $8$，所以他不希望这两个数字是集合 $B$ 中任意两个元素的差值。

具体来说，对于 $\forall x, y \in B, \; x - y \neq 5, \; x - y \neq 8$。（$\forall$ :任意的数学符号）

现在徐老师想要最大化集合 $B$ 的大小，你能告诉他集合 $B$ 的大小最大是多少吗？

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。

接下来的 $T$ 行，每行包含一个整数 $n$，表示集合 $A = \{1, 2, 3, \ldots, n\}$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

4
3
9
26
114514

3
5
12
52853

数据范围

• 对于 $30\%$ 的数据：$n \le 13, \; T \le 10$
• 对于 $60\%$ 的数据：$n \le 26$
• 对于 $100\%$ 的数据：$1 \le n \le 10^9, \; 1 \le T \le 10^5$