题目描述

小明不是很喜欢完全平方数，他甚至不喜欢加起来是完全平方数的两个数。

今天，他想从 $1$ 到 $X$ 中选择一些数组成一个集合，要求不选择任何一个完全平方数，集合中任意两个数相加也不能是完全平方数。请问，小明最多能选出多少个数。

输入描述

第一行包一个整数 $N$，表示测试数据的规模。

接下来 $N$ 行每行 $1$ 个整数 $X$。

输出描述

对每个输入输出一个整数表示答案。

2
5
20

3
9

评测用例规模与约定：

对于所有评测用例，$1≤X≤90, \sum X≤210$。

注：原题是直接输出 $X=100$ 时的结果。