Рассмотрим корневое неориентированное дерево. Каждую вершину можно раскрасить в синий, зелёный или жёлтый цвет. Раскраска называется красивой, если выполняются следующие условия:
Вам дано целое число $$$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$$$-й вершине. Существует ровно $$$3$$$ красивых раскрашивания: $$$[g, g]$$$, $$$[g, b]$$$ и $$$[g, y]$$$.
В третьем примере рассмотрим дерево-цепочку с $$$3$$$ вершинами и корнем в $$$1$$$-й вершине. Существует ровно $$$5$$$ красивых раскрашиваний: $$$[g, g, g]$$$, $$$[g, g, b]$$$, $$$[g, g, y]$$$, $$$[g, b, b]$$$ и $$$[g, y, y]$$$.
В пятом примере рассмотрим дерево с $$$3$$$ вершинами и корнем в $$$1$$$-й вершине, к которому присоединены остальные $$$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]$$$.
