import java.util.*;

/*
 * 표현 가능한 이진트리
 */

public class DH_150367 {
	static char[] tree;
	static int idx;
	
	static int[] solution(long[] numbers) {
		
		int[] answer = new int[numbers.length];
		
		for(int i = 0; i < numbers.length; i++) {
			if(numbers[i] == 0) {
				answer[i] = 0;
				continue;
			}
			
			// 입력된 수를 이진수 문자열로 바꿈
			String binaryString = numToBinaryStr(numbers[i]);

			int totalLength = binaryString.length();
			tree = new char[totalLength];
			setTree(binaryString, totalLength);
			answer[i] = check(tree) ? 1: 0;
		}
		
		return answer;
	}
	
	static String numToBinaryStr(long number) {
		String binaryString = Long.toBinaryString(number);
		
		// 포화 이진 트리를 구성하기 위해 필요한 노드의 총 개수
		int totalLength = getTotalLength(binaryString.length());
		
		// 추가로 더해야되는 0의 개수
		int addZeroLength = totalLength - binaryString.length();
		String addZerostr = "0".repeat(addZeroLength);
		
		// 이진트리로 표현할 수 있도록 문자열 가공해주기
		binaryString = addZerostr + binaryString;
		return binaryString;
	}
	
	// 표현 가능한 이진트리인지 확인
	static boolean check(char[] tree) {
		boolean available = true;
		
		// 부모노드가 0인데, 자식 노드가 하나라도 1이라면 표현 불가능한 이진트리
		// 확인해야 되는 부모 노드 idx: 0 ~ (마지막 depth - 1) 노드까지
		// 왜냐하면 마지막 depth 노드들은 자식이 없기 때문
		int depth = (int) (Math.log(tree.length) / Math.log(2)) + 1;
		int startIdx = (1 << (depth - 1)) - 1;
		
		for(int i = 0; i < startIdx; i++) {
			int currentIdx = i + 1;
			int next1 = currentIdx * 2;
			int next2 = currentIdx * 2 + 1;
			
			next1 -= 1; next2 -= 1;
			
			if(tree[i] == '0' && (tree[next1] == '1' || tree[next2] == '1')) {
				available = false;
				break;
			}
		}

		return available;
	}
	
	// inorder로 주어진 정보로 tree 구성하기
	static void setTree(String s, int totalLength) {
		idx = 0;

		Queue<int[]> q = new ArrayDeque<>();
		q.add(new int[] {0, totalLength + 1});
		
		while(!q.isEmpty()) {
			int[] current = q.poll();
			int l = current[0], r = current[1];
			if(l == r || r - l == 1) continue;

			int middle = (l + r) >> 1;
			tree[idx] = s.charAt(middle - 1);
			idx += 1;
			
			q.add(new int[] {l, middle});
			q.add(new int[] {middle, r});
		}
	}
	
	// 현재 트리의 크기가 length인 경우, 만들 수 있는 포화이진트리의 크기
	static int getTotalLength(int length) {
		int n = 1, digit = 0;
		
		while(true) {
			digit = (1 << n++) - 1;
			if(digit >= length) break;
		}
		
		return digit;
	}
	
	public static void main(String[] args) throws Exception {
		long[] numbers = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 128, 129, 16512, 2147516555L};
		System.out.println(Arrays.toString(solution(numbers)));
	}
}