Узумаки кауымда ауқымды фотосессия өтуде! Кауымда \(n\) адам бар, олардың әрқайсысы бірегей бойға ие, яғни \(1\)-ден \(n\)-ге дейінгі әрбір \(i\) үшін \(h_i = i\). Кейбіреулері — ақсүйектер, ал қалғандары — қарапайым кауым мүшелері.

Жалпы суретке түскеннен кейін кауым әрбір ақсүйегіне жеке топтық фотолар жасауды шешті. Алайда әрбір мұндай сурет мінсіз композицияға сәйкес келуі керек:

• Фотода тек бір ғана ақсүйек болуы тиіс.

• Одан төмен бойлы адамдар саны дәл одан биік бойлы адамдар санына тең болуы керек.

Әрбір ақсүйек өз маңына мінсіз композиция жасайтындай қатысушыларды жинай алады (немесе кадрда жалғыз қала алады). Суретке түскеннен кейін осы кадрдағы барлық қатысушылар фотосессиядан шығады, және бұл процесс қалған кауым мүшелерімен қайталанады.

Фотосессия сәтті өтуі үшін кауымның барлық мүшелері бір кадрға түсуі тиіс және ешкім суреттен тыс қалмауы керек.

Сіз, осы ауқымды фотосессияның ұйымдастырушысы ретінде, ақсүйектерге қатысушыларды тиімді бөлуде көмектесіп, фотосессияның сәтті өтуін қамтамасыз етуіңіз қажет немесе бұл мүмкін еместігін хабарлауыңыз керек.

Енгізу

Бірінші жолда бір бүтін сан \(t\) \((1 \leq t \leq 10^4)\) беріледі — кіріс деректер жиындарының саны. Кейін әрбір жиынның сипаттамасы беріледі.

Әрбір кіріс деректер жиыны ұзындығы \(n\) \((1 \leq n \leq 10^6)\) болатын \(s\) жолынан тұрады, ол тек '0' және '1' символдарынан құралған. Егер \(s[i] = 1\) болса, онда \(i\)-ші адам кауымның ақсүйегі, әйтпесе ол қарапайым мүше.

Кауымда кем дегенде бір ақсүйек бар екені кепілдендірілген, және барлық жолдардың жиынтық ұзындығы \(10^6\) аспайды.

Шығару

Әрбір кіріс деректер жиыны үшін, егер фотосессия сәтті өтуі мүмкін болса, "YES" шығарыңыз, әйтпесе "NO" шығарыңыз.

Мысалдар

Енгізу 1

4
1
1
5
10010
9
010001010
6
011000

Жауап 1

YES
NO
YES
NO

Ескертпелер

Үшінші кіріс деректер жиыны үшін, жол 010001010:

• ақсүйектер 2, 6 және 8 орындарында орналасқан.

• 2-орында тұрған ақсүйек үшін: 1 (төмен) және 4 (жоғары) бойлы қатысушыларды таңдаймыз \(\rightarrow\) топ \({1,2,4}\).

• 6-орында тұрған ақсүйек үшін: 3 және 5 (төмен) бойлы, 7 және 9 (жоғары) бойлы қатысушыларды таңдаймыз \(\rightarrow\) топ \({3,5,6,7,9}\).

• 8-орында тұрған ақсүйек үшін: тек өзі ғана \(\rightarrow\) топ \({8}\) (төмен бойлы 0, жоғары бойлы 0).

Барлық қатысушылар топтарға бөлінді, шарттар орындалды \(\Rightarrow\) жауап YES.