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]$。