CF2112E Tree Colorings

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