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 blue triangle
        if y > size:
            return 0  # Blue
        
        # If y == size, it's the tip of the inverted triangle which is red
        if y == size:
            return 1  # Red
        
        # 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 = list(map(int, input().split()))
Q = data[0]
results = []

# Process each query
for i in range(1, 2 * Q, 2):
    x = data[i]
    y = data[i + 1]
    results.append(get_color(x, y))

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