E. 树染色

每个测试点的时间限制：4 秒
每个测试点的内存限制：256 兆字节

考虑一棵有根无向树。每个顶点可以染成蓝色、绿色或黄色。一种染色被称为美丽的，如果它满足以下条件：

1. 树的根是绿色的；
2. 如果考虑所有蓝色和绿色的顶点，它们可以在不经过任何黄色顶点的情况下互相到达；
3. 如果考虑所有黄色和绿色的顶点，它们可以在不经过任何蓝色顶点的情况下互相到达。

给定一个整数 $m$。你的任务是计算一棵树中顶点的最小数量，使得这棵树恰好有 $m$ 种美丽的染色方案。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。
每个测试用例只有一行，包含一个整数 $m$（$1 \le m \le 5 \cdot 10^5$）。

输出
对于每个测试用例，输出一个整数 —— 具有恰好 $m$ 种美丽染色方案的最小顶点数。如果这样的树不存在，输出 $-1$。

示例
输入：

5
1
3
5
7
9

输出：

1
2
3
4
3

注释
在下面的注释中，用 $g$ 表示绿色，$b$ 表示蓝色，$y$ 表示黄色。

• 第一个样例：考虑一棵只有一个顶点的简单树。这棵树恰好有 $1$ 种美丽染色：根是绿色。
• 第二个样例：考虑一棵有 $2$ 个顶点的简单树，根是第 $1$ 个顶点。恰好有 $3$ 种美丽染色：$[g,g]$、$[g,b]$ 和 $[g,y]$。
• 第三个样例：考虑一棵有 $3$ 个顶点的链（竹子），根是第 $1$ 个顶点。恰好有 $5$ 种美丽染色：$[g,g,g]$、$[g,g,b]$、$[g,g,y]$、$[g,b,b]$ 和 $[g,y,y]$。
• 第五个样例：考虑一棵有 $3$ 个顶点的树，根是第 $1$ 个顶点，另外两个顶点都直接与根相连。恰好有 $9$ 种美丽染色：$[g,g,g]$、$[g,g,b]$、$[g,g,y]$、$[g,b,g]$、$[g,b,b]$、$[g,b,y]$、$[g,y,g]$、$[g,y,b]$ 和 $[g,y,y]$。