#include <iostream>
#include <cstdlib>
#include <string>
#include <vector>
#include <cctype>

    template <class Tc>
    bool next_digit(Tc& c)
    {
        return (std::isdigit(++c)) ? false :  (c = '0', true);
    }

    std::string solve(std::string& temp)
    {
        temp.erase(0, std::min(temp.find_first_not_of('0'), temp.size()-1));
        auto len = temp.length();
        auto itc = len/2;
        auto left = itc + len%2 - 1;
        auto right = len - left - 1;//- itc - len%2;

        bool carry = true;
        //  std::cout << carry << ":" << left << " - "<< right << '\n';
        if((left == right) /*&& (len > 1)*/)
        {
           if(temp[left-1] <= temp[right+1])
                carry = next_digit(temp[left]);

           if(len >= 3)
               left--, right++;
        }

        for(decltype(len) it = 0; it < itc; ++it)
        {
            //std::cout << carry << ":"<< left << " - "<< right << '\n';
            if(carry)
            {
                if(temp[left] > temp[right])
                {
                     carry = false;
                     temp[right++] = temp[left--];
                }
                else
                {
                     carry = next_digit(temp[left]);
                     temp[right++] = temp[left--];
                }
            }
            else
            {
                if(temp[left] == temp[right]) { carry = false; left--, right++; continue; }
                temp[right++] = temp[left--];
            }
        }

        if(carry) {
            temp = std::string(len+1, '0');
            temp[0] = '1';
            temp[len] = '1';
        }
        return temp;
    }

int main()
{
    int n = 0;

    std::cin  >> n;
    if (n <= 0)
        return EXIT_SUCCESS;

    std::vector<std::string> input(n);

    for (auto& str : input)
    {
        std::cin >> str;
    }

    for (auto& str : input)
    {
        auto answer = solve(str);

        std::cout << answer << std::endl;
    }

    return EXIT_SUCCESS;
}