题目描述

MX 有一个有 $(w-2)$ 个数的集合 $S=\{3,4,5,\cdots ,w\}$。要求构造一个只包含非负整数的集合（无重复元素），使得 $S$ 里面的任何一个数都能被这个集合里面大于等于 $3$ 个不同的数相加得到，求这个集合中至少包含多少个元素。

输入格式

本题包含多组测试数据。

第一行输入一个整数 $T$，表示数据组数。

接下来 $T$ 行每行输入一个整数 $w$。

输出格式

共 $T$ 行，每行输出一个整数 $n$，表示集合至少应该含有的元素个数。

1
4

4

5
3
18
999
9999
9999999999

3
6
12
15
35

提示

样例 1 说明：

集合元素可以为 $0,1,2,3$。

数据范围：

本题采用捆绑测试。

对于所有数据，保证 $1\le T \le 10^5$，$3\le w \le 10^{12}$。