module mod_hash_set
  implicit none
  integer, private, parameter :: intkind = 8
  integer, private, parameter :: int_max_value = 2147483647
  integer, private, parameter :: default_initial_capacity = 16
  integer, private, parameter :: maximum_capacity = lshift(1, 30)
  real, private, parameter :: default_load_factor = 0.75
  type t_element
    integer(intkind) :: key
    type(t_element), private, pointer :: next => null()
    integer, private :: hash
  end type
  type t_element_ptr
    type(t_element), pointer :: ref => null()
  end type
  type t_hash_set
    type(t_element_ptr), private, allocatable :: table(:)
    integer :: size = 0
    integer, private :: threshold = int(default_initial_capacity * default_load_factor)
    real, private :: load_factor = default_load_factor
  contains
    procedure :: is_empty => is_empty
    procedure :: is_not_empty => is_not_empty
    procedure :: add => add
    procedure :: add_all => add_all
    procedure :: remove => remove
    procedure :: clear => clear
    procedure :: contains => contains_key
    procedure :: get_keys => get_keys
  end type
  interface hash_set
    module procedure :: newhs0, newhs1, newhs2
  end interface
  interface urshift
    module procedure :: urshift0, urshift1
  end interface urshift
contains
  function new_element(key, h) result(res)
    integer(intkind), intent(in) :: key
    integer, intent(in) :: h
    type(t_element), pointer :: res
    allocate(res)
    res%key = key
    res%hash = h
  end
  integer function hash_code(key) result(res)
    integer(intkind), intent(in) :: key
    res = merge(xor(key, urshift(key, 32)), key, intkind == 8)
  end
  type(t_hash_set) function newhs0() result(res)
    allocate(res%table(default_initial_capacity))
  end
  type(t_hash_set) function newhs1(initial_capacity) result(res)
    integer, intent(in) :: initial_capacity
    res = newhs2(initial_capacity, default_load_factor)
  end
  type(t_hash_set) function newhs2(initial_capacity, load_factor) result(res)
    integer, intent(in) :: initial_capacity
    real, intent(in) :: load_factor
    integer :: capacity
    if (initial_capacity < 0) then
      capacity = default_initial_capacity
    else
      capacity = 1
      do while (capacity < min(initial_capacity, maximum_capacity))
        capacity = lshift(capacity, 1)
      end do
    end if
    if (load_factor <= 0 .or. load_factor /= load_factor) then
      res%load_factor = default_load_factor
    else
      res%load_factor = load_factor
    end if
    res%threshold = int(capacity * res%load_factor)
    allocate(res%table(capacity))
  end
  integer function urshift0(i, n) result(res)
    integer, intent(in) :: i
    integer, intent(in) :: n
    integer :: m
    m = and(n, 31)
    res = merge(i, rshift(ibclr(rshift(i, 1), 31), m - 1), m == 0)
  end
  integer(8) function urshift1(i, n) result(res)
    integer(8), intent(in) :: i
    integer, intent(in) :: n
    integer :: m
    m = and(n, 63)
    res = merge(i, rshift(ibclr(rshift(i, 1), 63), m - 1), m == 0)
  end
  integer function hash(i) result(res)
    integer, intent(in) :: i
    integer :: h
    h = xor(i, xor(urshift(i, 20), urshift(i, 12)))
    res = xor(h, xor(urshift(h, 7), urshift(h, 4)))
  end
  integer function index_for(h, length) result(res)
    integer, intent(in) :: h, length
    res = and(h, length - 1) + 1
  end
  logical function is_empty(this) result(res)
    class(t_hash_set), intent(in) :: this
    res = this%size == 0
  end
  logical function is_not_empty(this) result(res)
    class(t_hash_set), intent(in) :: this
    res = this%size /= 0
  end
  logical function contains_key(this, key) result(res)
    class(t_hash_set), intent(in) :: this
    integer(intkind), intent(in) :: key
    type(t_element), pointer :: e
    e => get_element(this, key)
    res = associated(e)
  end
  function get_element(this, key) result(res)
    class(t_hash_set), intent(in) :: this
    integer(intkind), intent(in) :: key
    integer :: h
    type(t_element), pointer :: e
    type(t_element), pointer :: res
    h = hash(hash_code(key))
    e => this%table(index_for(h, size(this%table)))%ref
    do while (associated(e))
      if (e%hash == h .and. e%key == key) then
        res => e
        return
      end if
      e => e%next
    end do
    res => null()
  end
  subroutine add(this, key)
    class(t_hash_set), intent(inout) :: this
    integer(intkind), intent(in) :: key
    integer :: h, i
    type(t_element), pointer :: e
    h = hash(hash_code(key))
    i = index_for(h, size(this%table))
    e => this%table(i)%ref
    do while (associated(e))
      if (e%hash == h .and. e%key == key) return
      e => e%next
    end do
    call add_element(this, key, h, i)
  end
  subroutine add_element(this, key, h, idx)
    class(t_hash_set), intent(inout) :: this
    integer(intkind), intent(in) :: key
    integer, intent(in) :: h, idx
    type(t_element), pointer :: e
    e => this%table(idx)%ref
    this%table(idx)%ref => new_element(key, h)
    this%table(idx)%ref%next => e
    this%size = this%size + 1
    if (this%size >= this%threshold) call resize(this, 2 * size(this%table))
  end
  subroutine add_all(this, keys)
    class(t_hash_set), intent(inout) :: this
    integer(intkind), intent(in) :: keys(:)
    integer :: new_capacity, threshold, i
    if (this%size + size(keys) >= this%threshold) then
      new_capacity = this%size
      threshold = this%threshold
      do while (this%size + size(keys) >= threshold)
        new_capacity = 2 * new_capacity
        threshold = int(new_capacity * this%load_factor)
      end do
      call resize(this, new_capacity)
    end if
    do i = 1, size(keys)
      call add(this, keys(i))
    end do
  end
  subroutine resize(this, new_capacity)
    class(t_hash_set), intent(inout) :: this
    integer, intent(in) :: new_capacity
    integer :: capacity, i, j
    type(t_element), pointer :: e, next
    type(t_element_ptr) :: table(new_capacity)
    capacity = size(this%table)
    if (capacity == maximum_capacity) then
      this%threshold = int_max_value
      return
    end if
    do j = 1, capacity
      e => this%table(j)%ref
      if (associated(e)) then
        this%table(j)%ref => null()
        do
          next => e%next
          i = index_for(e%hash, new_capacity)
          e%next => table(i)%ref
          table(i)%ref => e
          e => next
          if (.not.associated(e)) exit
        end do
      end if
    end do
    deallocate(this%table)
    allocate(this%table(new_capacity))
    do j = 1, new_capacity
      this%table(j)%ref => table(j)%ref
    end do
    this%threshold = int(new_capacity * this%load_factor)
  end
  subroutine remove(this, key)
    class(t_hash_set), intent(inout) :: this
    integer(intkind), intent(in) :: key
    integer :: h, i
    type(t_element), pointer :: e, prev, next
    h = hash(hash_code(key))
    i = index_for(h, size(this%table))
    prev => this%table(i)%ref
    e => prev
    do while (associated(e))
      next => e%next
      if (e%hash == h .and. e%key == key) then
        this%size = this%size - 1
        if (associated(prev, e)) then
          this%table(i)%ref => next
        else
          prev%next => next
        end if
        return
      end if
      prev => e
      e => next
    end do
  end
  subroutine clear(this)
    class(t_hash_set), intent(inout) :: this
    if (allocated(this%table)) deallocate(this%table)
    allocate(this%table(default_initial_capacity))
    this%size = 0
  end
  function get_keys(this) result(res)
    class(t_hash_set), intent(in) :: this
    integer(intkind) :: res(this%size)
    integer :: i, k
    type(t_element), pointer :: e
    k = 0
    do i = 1, size(this%table)
      e => this%table(i)%ref
      do while (associated(e))
        k = k + 1
        res(k) = e%key
        e => e%next
      end do
    end do
  end
end module mod_hash_set
program xor_battle
  use mod_hash_set
  implicit none
  integer :: t, n, i, j, k, cnt(0:1)
  integer(8) :: a(200) = 0, b(200, 0:1)
  character(200) :: s
  logical :: f
  type(t_hash_set) :: set
  read(*,*) t
  do k = 1, t
    read(*,*) n
    read(*,*) a(1:n)
    read(*,*) s
    cnt = 0
    b = 0
    do i = 1, n
      j = ichar(s(i:i)) - 48
      cnt(j) = cnt(j) + 1
      b(cnt(j), j) = a(i)
    end do
    if (any(cnt == 0)) then
      write(*,'(i0)') merge(1, 0, cnt(0) == 0)
      cycle
    end if
    cnt(0) = reduce(b(1:cnt(0), 0))
    cnt(1) = reduce(b(1:cnt(1), 1))
    call set%clear()
    call set%add_all(b(1:cnt(0), 0))
    f = any([(.not.set%contains(b(i, 1)), i = 1, cnt(1))])
    write(*,'(i0)') merge(1, 0, f)
  end do
contains
  integer function reduce(x) result(res)
    integer(8), intent(inout) :: x(:)
    integer :: n, i, j, k, l
    n = size(x)
    j = 0
    do i = 1, n
      do while (j <= 63 .and. all(.not.btest(x(i:n), j)))
        j = j + 1
      end do
      if (j > 63) then
        res = i - 1
        return
      end if
      if (.not.btest(x(i), j)) then
        do k = i + 1, n
          if (btest(x(k), j)) then
            l = k
            exit
          end if
        end do
        call swap(x(i), x(l))
      end if
      do k = 1, n
        if (k == i) cycle
        if (btest(x(k), j)) x(k) = xor(x(k), x(i))
      end do
    end do
    res = n
  end
  subroutine swap(a, b)
    integer(8), intent(inout) :: a, b
    a = xor(a, b)
    b = xor(a, b)
    a = xor(a, b)
  end
end program xor_battle