"""
출처:프로그래머스,
https://school.programmers.co.kr/learn/courses/30/lessons/150367
"""
# 풀이 과정
# 왼쪽 자식 노드가 1일때 오른쪽 노드는 반드시 1이고,부모노드 또한 1이어야한다 이걸 바탕으로 확인해야한다
from collections import deque


def solution(numbers):
    result = []
    n = numbers

    for i in n:
        k = bin(i)[2:]

        l = len(k)

        # 포화이진 트리 찾기
        h = 0  # 깊이
        count = 0

        while count < l:
            count += 2 ** h
            h += 1

        # 포화 이진트리로 모형으로 변환
        k = "0" * (count - l) + k

        # 맨 처음 노드 번호
        start = (len(k) + 1) // 2 - 1  # -1인이유: 인덱스 번호
        d = (start + 1) // 2
        # print(start,i, "start")
        q = deque([start])

        m = [False for _ in range(len(k))]
        flag = False

        son = []  # 자식노드 모음
        while True:
            arrive = q.popleft()
            a = arrive
            # 방문 확인
            m[a] = True
            # 부모 노드 0일때
            if k[a] == "0":
                if 0 <= a + d < len(k) and k[a + d] == "1" and m[a + d] == False:
                    # print(1,i,"d:",d,"a :",a,"a+d:",a+d)
                    flag = True
                    break
                elif 0 <= a + d < len(k) and k[a + d] == "0" and m[a + d] == False:
                    # print(2,i)
                    son.append(a + d)

                if 0 <= a - d < len(k) and k[a - d] == "1" and m[a - d] == False:
                    # print(3,i)
                    flag = True
                    break
                elif 0 <= a - d < len(k) and k[a - d] == "0" and m[a - d] == False:
                    # print(4,i)
                    son.append(a - d)
            else:

                if 0 <= a + d < len(k) and m[a + d] == False:
                    son.append(a + d)
                if 0 <= a - d < len(k) and m[a - d] == False:
                    son.append(a - d)

            if len(q) == 0:
                if len(son) == 0:
                    break
                else:
                    q += son
                    d //= 2
                    son = []
            # print(q)

        if flag == True:
            result.append(0)
            # print("--------",i,"result")
        else:
            result.append(1)
            # print("--------",i,"result")
    return result