Consider a rooted undirected tree. Each vertex can be colored blue, green, or yellow. A coloring is called beautiful if it meets these conditions: the root of the tree is green; if you consider all blue and green vertices , they are reachable from each other without passing through any yellow vertices; if you consider all yellow and green vertices , they are reachable from each other without passing through any blue vertices; You are given an integer (m). Your task is to calculate the minimum number of vertices in a tree with exactly (m) beautiful colorings. The first line contains a single integer ((1 \le t \le 10^5)) — the number of test cases. The only line of each test case contains a single integer (m) ((1 \le m \le 5 \cdot 10^5)). For each test case, print a single integer — the minimum number of vertices in a tree with exactly (m) beautiful colorings. If such a tree does not exist, print (-1). In the following notes, let (g) describe green color, (b) be blue, and (y) be yellow. In the first example, consider a simple tree with just (1) vertex. This tree has exactly (1) beautiful coloring: the root is green. In the second example, consider a simple tree with (2) vertices with a root at the (1)-st vertex. There are exactly (3) beautiful colorings: (g, g), (g, b) and (g, y). In the third example, consider a bamboo tree with (3) vertices with a root at the (1)-st vertex. There are exactly (5) beautiful colorings: (g, g, g), (g, g, b), (g, g, y), (g, b, b) and (g, y, y). In the fifth example, consider a tree with (3) vertices with a root at the (1)-st vertex, and the other (2) vertices connected to it. There are exactly (9) beautiful colorings: (g, g, g), (g, g, b), (g, g, y), (g, b, g), (g, b, b), (g, b, y), (g, y, g), (g, y, b) and (g, y, y).