Words

اگر ‎$w$‎ یک رشته از کاراکترهای ‎$0$‎ و ‎$1$‎ باشد، ‎$h(w)$‎ رشته‌ای است که به‌جای هر کاراکتر ‎$0$ از $w$‎ یک کاراکتر ‎$1$‎ قرار می‌دهد و به‌جای هر کاراکتر ‎$1$ از $w$‎ یک رشته ‎$10$‎ قرار می‌دهد. برای مثال ‎$h(1001)$‎ برابر است با ‎$101110$. حال توابع زیر از روی ‎$h$‎ تعریف می‌شود:

• ‎ $h^0(w) = w$‎
• ‎ $h^1(w) = h(w)$‎
• ‎ $h^{k > 1}(w) = h(h^{k-1}(w))$‎

به شما ‎$n$‎ عدد ‎$k_1$‎ تا ‎$k_n$‎ داده شده است، شما باید تحقیق کنید آیا عدد ‎$m$‎ وجود دارد که رشته ‎$h^{k_1}(0)+h^{k_2}(0)+\cdots+h^{k_n}(0)$‎ زیررشته ای از ‎$h^m(0)$‎ باشد یا نه.

‎ ‎$a+b$‎ رشته‌ای است که از کنار هم قرار دادن دو رشته ‎$a$‎ و ‎$b$‎ به‌دست می آید‎.

• در سطر اول ورودی، عدد ‎$1 \leq t \leq 10$‎ نشان‌دهنده تعداد تست‌ها آمده است.
• در سطر اول هر تست، عدد ‎$1 \leq n \leq 10^5$‎ آمده است.
• در سطر دوم هر تست، ‎$n$‎ عدد ‎$k_1$‎ تا ‎$k_n$‎ آمده‌اند.
• تمام اعداد ورودی کم‌تر یا مساوی ‎$10^9$‎ هستند.‎

به ازای هر تست در صورتی که عدد ‎$m$‎ وجود دارد عبارت ‎TAK‎ و در غیر این صورت عبارت ‎NIE‎ را چاپ کنید.

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل