题解 | #牛牛的10类人#

import sys


def classify_numbers(n, numbers):
    results = []  # 用于存储每个数的分类结果

    for num in numbers:
        # 将数转换为二进制字符串
        binary_representation = bin(num)[2:]

        # 计算 1 和 0 的数量
        count_1 = binary_representation.count("1")
        count_0 = binary_representation.count("0")

        # 分类
        is_one_even = count_1 % 2 == 0
        is_zero_even = count_0 % 2 == 0

        if is_one_even and is_zero_even:
            results.append("10")
        elif is_one_even:
            results.append("1")
        elif is_zero_even:
            results.append("0")
        else:
            results.append("100")

    return " ".join(results)


def main():
    input = sys.stdin.read
    data = input().strip().split()

    n = int(data[0])
    numbers = [int(data[i]) for i in range(1, n + 1)]

    result = classify_numbers(n, numbers)
    print(result)


if __name__ == "__main__":
    main()