题目描述

国际象棋中，一方的皇后数不能超过 $5$ 个。现在给定一个 $N \times N$ 的棋盘，任意摆放皇后，问最坏情况下最少需要多少个皇后才能保证所有的格子都被攻击到。

输入格式

多组数据。 第一行一个整数 $T$，表示数据组数。 接下来 $T$ 行，每行一个正整数 $N$，表示棋盘大小。

输出格式

每组数据输出一行一个整数表示答案。

输入样例

1
3

输出样例

3

提示

$100\%$ 的数据，$N \le 50$，$T \le 25$。