Bittijono

import java.util.Scanner;

public class Bittijono {
	private static final int[] first16 = {1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1};

	public static void main(String[] args) {
		Scanner reader = new Scanner(System.in);
		int loop = reader.nextInt();
		int i;
		long[] numbers = new long[loop];
		for (i=0;i<loop;i++)
			numbers[i] = reader.nextLong();
		for (i=0;i<loop;i++) {
			if (findNumber(numbers[i]) == -1)
				System.out.println(1);
			else
				System.out.println(0);
		}
		reader.close();
	}
	
	private static long findNumber(long index) {
		if (index == 0)
			return -1;
		if (index<17)
			return first16[(int) (index-1)];
		long i = 0;
		for(i=1;i*4<index;i*=4);
		int blockNumber = (int) -Math.floorDiv(-index, i);
		return findNumber(index - (blockNumber-1) * i) * first16[blockNumber-1];
	}

}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 2

Verdict: ACCEPTED

Test 3

Group: 3

Verdict: ACCEPTED