Трёх Битовый Компьютер
Ученые королевства Байтланд хотят разработать новый тип компьютера, а именно Трех Битовый Компьютер (ТБК). Они прогнозируют, что новая машина будет способна решить много трудных и неразрешимых до этого задач. Однако имеется несколько технических проблем, которые сначала следует решить. Вас попросили ассистировать ученым в решении одной из них.
Ученые на данный момент работают над процедурой инициализации памяти компьютера. Текущая версия ТБК имеет n бит памяти, пронумерованных от 1 до n. Каждый бит может принимать одно из трех значений a, b, c или быть не инициализированным. Следующие операции по инициализации памяти поддерживаются компьютером:
два последовательных неинициализированных бита, то есть биты с номерами i и i+1 для 1 ≤ i < n, могут быть установлены в два различных значения,
два последовательных бита, один неинициализированный, второй установленный в значение x, могут быть установлены в два различных значения, отличных от x.
Например, возможна следующая последовательность инициализаций для n = 4, uuuu → uuab → ucbb → babb, где u обозначает неинициализированный бит памяти.
Задание
Напишите программу, которая:
читает значения, которыми следует инициализировать память,
проверяет возможна ли инициализация,
выводит ответ.
Входные данные
Первая строка содержит количество тестов n (1 ≤ n ≤ 10). Каждый тест состоит из шаблона, который задается в двух строках. Первая строка содержит натуральное число l_i (1 ≤ l_i ≤ 100000) - длину i-го шаблона (то есть размер памяти компьютера). Вторая строка содержит последовательность из букв a, b, c длины l_i - сам шаблон.
Выходные данные
Вывести n строк, по одной для каждого теста. i-ая строка должна содержать одно слово YES, если указанная инициализация возможна и NO иначе.