阶乘平方数

题目描述

Y 同学需要处理若干次关于阶乘的查询。

对于一个正整数 $x$，定义 $x!$ 为

$x!=1\times2\times\cdots\times x$。

如果存在非负整数 $y$，使得一个整数 $z$ 满足 $z=y^2$，则称 $z$ 为完全平方数。

对于每次查询，给定一个正整数 $n$。请找出所有满足以下条件的正整数 $x$：

• $x!+1\le n$；
• $x!+1$ 是一个完全平方数。

对于每次查询，请按照从小到大的顺序输出所有满足条件的 $x$。

输入格式

第一行包含一个整数 $T$，表示查询组数。

接下来 $T$ 行，每行包含一个整数 $n$，表示该次查询的上界。

输出格式

对于每次查询，输出一行。

若存在满足条件的正整数 $x$，则按照从小到大的顺序输出所有满足条件的 $x$，相邻两个整数之间用一个空格分隔。

若不存在满足条件的正整数 $x$，则输出 -1。

样例

样例输入 #1

3
1
25
5041

样例输出 #1

-1
4
4 5 7

样例解释

第一组查询 $n=1$，任意正整数 $x$ 都有 $x!+1\ge 2>1$，不存在满足条件的 $x$，输出 -1。

第二组查询 $n=25$，$4!+1=25=5^2$ 是完全平方数且不超过 $25$，满足条件；而 $5!+1=121>25$ 已经超出上界，所以只输出 $4$。

第三组查询 $n=5041$，$4!+1=25=5^2$，$5!+1=121=11^2$，$7!+1=5041=71^2$，三者都是完全平方数且不超过 $5041$；而 $6!+1=721$ 虽然不超过 $5041$，但它不是完全平方数，所以输出 $4,5,7$。

样例输入 #2

2
121
1000000000000000000

样例输出 #2

4 5
4 5 7

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1\le T\le 5\times10^4$；
• $1\le n\le 10^{18}$。

• 特殊性质 A：保证所有查询均满足 $n<25$。
• 特殊性质 B：保证所有查询中的 $n$ 两两不同。
• 特殊性质 C：保证查询序列中的 $n$ 单调不降。