题目内容

给定一个正整数 $n$（数值范围可能极大），请找出所有满足以下两个条件的正整数 $x$：

1. $x! + 1 < n$
2. $x! + 1$ 是一个完全平方数

要求输出所有满足条件的 $x$ 值。若不存在满足条件的 $x$，则输出相应提示。

输入描述

第一行输入一个整数 $T$（$1 \leq T \leq 5 \times 10^4$），表示查询的组数。

接下来 $T$ 行，每行输入一个整数 $n$（$1 \leq n \leq 10^{18}$），表示该组查询的上界。

输出描述

对每组查询输出一行，按从小到大的顺序输出所有满足条件的 $x$，相邻两个数之间用一个空格分隔。

若该组查询不存在满足条件的 $x$，则该行输出 $-1$。

样例1

输入

3
1
25
5041

输出

-1
4
4 5 7

说明

第一组查询 $n = 1$，任意正整数 $x$ 都有 $x! + 1 \geq 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

输出

4 5
4 5 7

说明

第一组查询 $n = 121$，$4! + 1 = 25$ 与 $5! + 1 = 121$ 都不超过 121 且都是完全平方数，而 $7! + 1 = 5041 > 121$ 被排除，所以输出 4, 5。

第二组查询 $n = 10^{18}$，在 $x! + 1 < 10^{18}$ 的范围内（即 $x \leq 19$）只有 $x$ 取 4, 5, 7 时 $x! + 1$ 是完全平方数。