CF2112E.Tree Colorings

考虑一棵有根树，每个结点可以被染成蓝色、绿色或黄色。一个染色方案是美丽的，当且仅当：

• 根节点被染成绿色；
• 所有的蓝色和绿色结点构成一个点集，点集中的点两两之间的路径上都没有黄色结点；
• 所有的黄色和绿色结点构成一个点集，点集中的点两两之间的路径上都没有蓝色结点。

给你一个整数 $m$，问一棵恰有 $m$ 种美丽的染色方案的有根树最少有多少个结点？

多组数据。第一行一个整数 $t(1\le t\le 10^5)$ 表示数据组数。

对于每组数据，一行一个整数 $m(1\le m\le 5\times 10^5)$。

对于每组数据，输出一个整数表示答案。特别地，如果不存在一棵恰有 $m$ 种美丽的染色方案的有根树，在这一行输出 $-1$。

样例解释

我们用 $g$ 表示绿色，用 $b$ 表示蓝色，用 $y$ 表示黄色。

对于第一组数据，考虑一个只有一个结点的树。它有一种美丽的染色方案：根节点为绿色。

对于第二组数据，考虑一个有两个结点的树，根为结点 $1$，它有三种美丽的染色方案：$[g,g],[g,b],[g,y]$。

对于第三组数据，考虑一个有三个结点的链，根为结点 $1$，结点 $2$ 和结点 $1$ 与结点 $3$ 相连，它有五种美丽的染色方案：$[g,g,g],[g,g,b],[g,g,y],[g,b,b],[g,y,y]$。

方案 $[g,b,g]$ 和 $[g,y,g]$ 是无效的，分别不满足第三个条件和第二个条件。因为从底部顶点到顶部节点的路径中，不满足点集中的点两两之间的路径上都没有黄色或蓝色结点。

对于第五组数据，考虑一个有三个结点的树，根为结点 $1$，另外两个结点和它相连，它有九种美丽的染色方案：$[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]$。