考虑一棵有根无向树。每个顶点可以着色为蓝色、绿色或黄色。有一种着色叫做 美丽 如果满足以下条件:
- 树的根是绿色的;
- 如果你考虑 所有蓝色和绿色顶点,它们无需经过任何 黄色 顶点;
- 如果你考虑 所有黄色和绿色顶点,它们无需经过任何 蓝色 顶点;
给你一个整数 $$$m$$$。您的任务是计算树中的最小顶点数 正是 $$$m$$$ 美丽 着色。
输入
第一行包含一个整数 ($$$1 \le t \le 10^5$$$) — 测试用例的数量。
每个测试用例的唯一行包含一个整数 $$$m$$$ ($$$1 \le m \le 5 \cdot 10^5$$$)。
输出
对于每个测试用例,打印一个整数 - 树中顶点的最小数量 正是 $$$m$$$ 美丽 着色。如果这样的树不存在,则打印$$$-1$$$。
示例
输入复制
513579
输出复制
1 2 3 4 3
注意
在下面的注释中,让 $$$g$$$ 描述绿色,$$$b$$$ 描述蓝色,$$$y$$$ 描述黄色。
在第一个示例中,考虑一棵只有 $$$1$$$ 顶点的简单树。这棵树有 $$$1$$$ 漂亮的颜色:根是绿色的。
在第二个示例中,考虑一棵具有 $$$2$$$ 顶点且根位于 $$$1$$$-st 顶点的简单树。总共有 $$$3$$$ 漂亮的颜色:$$$[g, g]$$$、$$$[g, b]$$$ 和 $$$[g, y]$$$。
在第三个示例中,考虑一棵具有 $$$3$$$ 顶点、根位于 $$$1$$$-st 顶点的竹树。恰好有 $$$5$$$ 漂亮的颜色:$$$[g, g, g]$$$、$$$[g, g, b]$$$、$$$[g, g, y]$$$、$$$[g, b, b]$$$ 和 $$$[g, y, y]$$$。
在第五个示例中,考虑一棵具有 $$$3$$$ 顶点的树,根位于 $$$1$$$-st 顶点,其他 $$$2$$$ 顶点连接到它。正好有$$$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]$$$。