def get_color(x, y):
    while x > 1:
        # Calculate the size of the triangle at step x
        size = (1 << (x - 1)) - 1  # size = 2^(x-1) - 1
        
        # Check if (x, y) is in the inverted triangle
        if y > size:
            return 0  # Blue
        
        # Determine if we are in the left or right triangle
        if y == size:
            return 1  # Red (the point at the tip of the inverted triangle)
        
        # Move to the previous triangle
        x -= 1
        
        # Adjust y for the next layer
        if y > size // 2:
            y -= (size // 2 + 1)  # Move to the right triangle
        # If y <= size // 2, we stay in the left triangle

    return 1  # If we reach step 1, it is always red

import sys

# Read input
input = sys.stdin.read
data = input().splitlines()
Q = int(data[0])
results = []

for i in range(1, Q + 1):
    x, y = map(int, data[i].split())
    results.append(get_color(x, y))

# Print results
print("\n".join(map(str, results)))