Задача Game2020. Улюблена справа колядників - ділити зароблені солодощі та гроші. Олесь та Михась отримали купу цукерок, а крім того грошову купюру певного номіналу. Звісно що ця купюра представляє для хлопців найбільший інтерес, а дорослих, які б могли розміняти суму порівно, немає. Тому старшим братом було запропоновано зіграти у наступну гру.
Кожному з гравців по черзі доводиться обирати деякий непорожній набір кошиків з ряду (таких, що стоять поруч), а далі з кожного необхідно забрати щонайменше по одній цукерці. Такі дії гравці роблять, поки у когось не залишиться можливості зробити хід - тоді цей гравець програє і гроші дістаються переможцю.
Михась вже розклав цукерки по кошикам, але Олесь підозрює, що брат заздалегідь точно знає, що зможе виграти. Олесь, як молодший брат, ходить першим і просить у вас допомоги - чи зможе має він деяку виграшну стратегію для заданого набору цукерок?
Технічні умови З першого рядку стандартного пристрою введення програма Game2020 зчитує єдине число T (1 ≤ T ≤ 10) - кількість тестів. Далі, у T парах рядків слідують вхідні дані у вигляді:
- У першому в парі - число N (1 ≤ N ≤ 106) - кількість кошиків з цукерками
- У другому в парі - N чисел Ai (0 ≤ Ai ≤ 105) - кількість цукерок у кошиках
Програма має вивести рядок з рівно N символів - відповіді на кожен з тестів у тій самій послідовності, що і у вхідних даних. Програма має вивести Y, якщо у Михась точно має стратегію для перемоги і N у іншому випадку.
Приклади
|
Введення |
Виведення |
Коментар |
|
3 3 1 0 1 4 1 5 6 1 5 1 0 1 1 1 |
YNN |
У першому випадку Олесь має опорожнити один з кошиків, після чого Михась забере цукерку з іншого і виграє. У другому випадку Олесь може забрати усі цукерки одразу, чим забезпечить перемогу. У третьому випадку Олесь може опорожнити два з трьох кошиків, що йдуть підряд, після чого Михасю доведеться взяти цукерку з одного з кошиків, що залишились, що дасть перемогу Олесю. |