1011. 奶蛙的奶糖

题目描述

奶娃正在给奶糖编号，他想让奶龙吃掉某些特定的奶糖，将会被变成奶蛙。对于一个正整数 N，奶娃把它写成二进制，并定义：

• N ≫ 1：把 N 的二进制整体右移一位；

• popcount(N )：N 的二进制表示中数字 1 的个数。

如果一个编号满足

popcount(N )3 = N ≫ 1,奶娃就认为它是一个“立方奶糖编号”。现在有 q 次询问。每次给出一个正整数 x，请找到不小于 x 的最小立方奶糖编号 N，并需要满足 N ≤ 109。如果不存在这样的 N，输出 −1。

输入格式

第一行输入一个整数 q，表示询问次数。接下来 q 行，每行输入一个整数 x，表示一次询问。

1 ≤ q ≤ 105,1 ≤ x ≤ 109 .所有变量均为整数。

输出格式

对于每次询问，输出一行一个整数：

• 若存在满足条件的最小整数 109 ≥ N ≥ x，输出这个 N；

• 否则输出 −1。

样例输入

2
16
1000000000

样例输出

17
-1

来源：官方题面 PDF（2026"钉耙编程"暑期联赛 第10场）