// Arup Guha
// 3/7/2016
// Solution to 2016 UCF HS Problem: Too Much to Two

import java.util.*;

public class two {

    public static void main(String[] args) {

        // We will pre-compute all necessary values and store them in a Tree Set, so that it's
        // very easy to obtain the next value in the set strictly greater than some input value.
        TreeSet <Integer> hypereven = new TreeSet<Integer>();
        int last = -1;

        // Since we need two positive splits, we can start at 11.
        for (int cur=11;; cur++) {

            // Once we find a hypereven number past 2^15, we can stop!
            if (last > 32768) break;

            // Check it - only add if it passes.
            if (isHyperEven(cur)) {
                hypereven.add(cur);
                last = cur;
            }
        }

        Scanner stdin = new Scanner(System.in);
        int numCases = stdin.nextInt();

        // Process each case.
        for (int loop=0; loop<numCases; loop++) {
            int query = stdin.nextInt();
            System.out.println("The next hyper-even after "+query+" is "+hypereven.higher(query));
        }
    }

    public static boolean isHyperEven(int n) {

        // To test if we can just add 1 power of 2 to this number.
        int saven = n;

        // Strip least significant zeroes.
        while ((saven & 1) == 0) saven = saven >> 1;

        // The adding property only holds true if adding a single 1 to this value yields a
        // perfect power of 2.
        if (Integer.bitCount(saven+1) != 1) return false;

        // Makes life easier - or we can do mod 10, 100, 1000, etc.
        String s = new String(""+n);

        for (int i=1; i<s.length(); i++) {

            // Get both ints.
            int left = Integer.parseInt(s.substring(0,i));
            int right = Integer.parseInt(s.substring(i));

            // Skip if either isn't a perfect power of 2.
            if (Integer.bitCount(left) != 1) continue;
            if (Integer.bitCount(right) != 1) continue;

            // If we get here it works!
            return true;
        }

        // If we get here, it doesn't.
        return false;
    }
}