我们知道，229=5368709122^{29}=536870912 是小于 10910^9 的最大 22 的方幂。

所以我们每次只需要枚举 2n[0≤n≤30]2^n[0\le n\le30]，找到符合条件的输出即可。

时间复杂度 O(30T)O(30T)，可以通过。

代码。