Three Bit Computer#4379
The scientists in the Kingdom of Byteland want to develop a new type of computer, namely the Three Bit Computer (TBC). They predict that the new machine will have the power to solve many hard and still unsolved problems. However, there are some technical difficulties that have to be resolved first. You have been asked to assist the scientists in solving one of them.
The scientists are now working on the initialization procedure for the computer memory. The current version of the TBC has bits of memory, numbered from to . Each bit can have one of three values , , , or might be uninitialized. The computer supports the following memory initialization operations:
- Two consecutive uninitialized bits, i.e., the bits numbered and i+1 for 1 \leq i < n, can be set to two different values. - Two consecutive bits, one uninitialized and one initialized to value , can be set to two different values not equal to .
For example, the following initialization procedure is possible for n = 4: uuuu \rightarrow uuab \rightarrow ucbb \rightarrow babb, where denotes an uninitialized bit of memory.
Task:
Write a program that: - reads the values to which the memory has to be initialized, - checks if the initialization is possible, - writes the answer to the output file.
The first line of the input file contains a single positive integer (1 \leq n \leq 10), the number of patterns. The description of the patterns follows. The description of a single pattern consists of two consecutive lines. The first line contains a positive integer l_i (1 \leq l_i \leq 100\,000), the length of the -th pattern (i.e., the size of the computer's memory). The second line contains a sequence of length l_i consisting of the letters , , — the pattern itself.
The output file should have lines, one for each pattern. The -th line should contain a single word YES if the initialization is possible, or NO otherwise.
Beispiel 1