use std::collections::VecDeque;
use std::fs::File;
use std::io::Write;
use std::io::{self, BufRead};

fn check(nums: &Vec<i32>, i: usize, next: &mut VecDeque<i32>) -> bool {
    // println!("i={} Nums: {:?} next: {:?}", i, nums, next);

    if i >= nums.len() {
        // println!("returning for reaching end: {}", next.is_empty());
        return next.is_empty();
    } else if next.is_empty() {
        // println!("not at end but nexxt is empty");
        return false;
    }

    let elem = next.pop_front().unwrap();

    if elem < 10 {
        if elem == nums[i] {
            let result = check(nums, i + 1, next);
            next.push_front(elem); // push back the element
            return result;
        } else {
            next.push_front(elem); // push back the element
            return false;
        }
    }

    if elem == 10 {
        // A
        let result = check(nums, i + 1, next);
        if result {
            return true;
        }
    } else if elem == 20 {
        if nums[i] == 2 {
            // transform to 2B
            next.push_front(20);
            if check(nums, i + 1, next) {
                return true;
            }
            next.pop_front().unwrap(); // remove 20
        } else if nums[i] == 1 {
            // transform to 1A3AC
            next.push_front(30); // push C
            next.push_front(10); // push A
            next.push_front(3); // push 3
            next.push_front(10); // push A
            if check(nums, i + 1, next) {
                return true;
            }
            next.pop_front().unwrap(); // remove A
            next.pop_front().unwrap(); // remove 3
            next.pop_front().unwrap(); // remove A
            next.pop_front().unwrap(); // remove C
        }
    } else if elem == 30 {
        if nums[i] == 2 {
            if check(nums, i + 1, next) {
                // transform to 2
                return true;
            }
        } else if nums[i] == 3 {
            // transform to 3BC
            next.push_front(30); // push C
            next.push_front(20); // push B
            if check(nums, i + 1, next) {
                return true;
            }
            next.pop_front().unwrap(); // remove B
            next.pop_front().unwrap(); // remove C
        } else if nums[i] == 1 {
            // transform to 12A
            next.push_front(10); // push A
            next.push_front(2); // push 2
            if check(nums, i + 1, next) {
                return true;
            }
            next.pop_front().unwrap(); // remove 2
            next.pop_front().unwrap(); // remove A
        }
    }

    next.push_front(elem);

    false
}

fn solve(nums: Vec<i32>) -> bool {
    let mut next = VecDeque::from([10]);
    if check(&nums, 0, &mut next) {
        return true;
    }
    next = VecDeque::from([20]);
    if check(&nums, 0, &mut next) {
        return true;
    }
    next = VecDeque::from([30]);
    if check(&nums, 0, &mut next) {
        return true;
    }

    return false;
}

fn main() {
    let input = File::open("perle.in").expect("Unable to open file");
    let mut out = File::create("perle.out").expect("Unable to create file");

    // read T
    let mut reader = io::BufReader::new(input);
    let mut line = String::new();
    reader.read_line(&mut line).expect("Unable to read line");

    let t: usize = line.trim().parse().expect("Invalid number of test cases");

    for _i in 0..t {
        line = String::new();
        reader.read_line(&mut line).expect("Unable to read line");

        let nums: Vec<i32> = line
            .split_whitespace()
            .filter_map(|s| s.parse::<i32>().ok())
            .skip(1)
            .collect();

        let ok = solve(nums);
        if ok {
            writeln!(out, "1").expect("Unable to write to file");
        } else {
            writeln!(out, "0").expect("Unable to write to file");
        }
    }
}