- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
امین یک معادله ساده به فرم \(A + B = C\) روی تخته نوشته بود. یک روز مهلا تصمیم میگیرد کاراکترهای + و = را پاک کند و سه قسمت \(A\)، \(B\) و \(C\) را بهم بچسباند. حالا امین به سراغ تخته میآید و میخواهد از روی این رشتهی ارقام معادله را بازسازی کند.
در واقع امین با یک رشته \(n\) رقمی از ارقام ۱ تا ۹ مواجه است و میخواهد این رشته را به سه بازهی متوالی \(A\)، \(B\) و \(C\) تقسیم کنیم به طوری که معادلهی \(A + B = C\) برقرار باشد. او از شما میخواهد بررسی کنید آیا انجام چنین افرازی ممکن است یا نه.
ورودی
در سطر اول ورودی، عدد صحیح و مثبت \(t\) که تعداد سناریوها را نشان میدهد، داده میشود.
\[1 \leq t \leq 100 \, 000\]
در سطر اول هر سناریو، عدد صحیح و مثبت \(n\) آمده که طول رشته را نشان میدهد.
\[1 \leq n \leq 500 \, 000\]
در سطر دوم هر سناریو، یک رشته از ارقام 1 تا 9 به نام \(s\) داده میشود.
تضمین میشود که \(\sum n \leq 1000\,000\) باشد.
خروجی
در \(t\) سطر برای هر سناریو، در صورتی که میتوان چنین تقسیمی انجام داده YES و در غیر این صورت NO چاپ کنید.
مثالها
ورودی نمونه ۱
3
3
123
6
123456
11
14323242467
خروجی نمونه ۱
YES
NO
YES
معادلهی سناریو اول به صورت
\[1 + 2 = 3\]
بوده است. بنابراین پاسخ YES میشود.
معادلهای برای سناریو دوم وجود ندارد
معادلهی سناریو سوم به صورت
\[143 + 2324 = 2467\]
بوده است. بنابراین پاسخ YES میشود.