معادله تخریب شده


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

امین یک معادله ساده به فرم A+B=CA + B = C روی تخته نوشته بود. یک روز مهلا تصمیم می‌گیرد کاراکترهای + و = را پاک کند و سه قسمت AA، BB و CC را بهم بچسباند. حالا امین به سراغ تخته می‌آید و می‌خواهد از روی این رشته‌ی ارقام معادله را بازسازی کند.

در واقع امین با یک رشته nn رقمی از ارقام ۱ تا ۹ مواجه است و می‌خواهد این رشته را به سه بازه‌ی متوالی AA، BB و CC تقسیم کنیم به طوری که معادله‌ی A+B=CA + B = C برقرار باشد. او از شما می‌خواهد بررسی کنید آیا انجام چنین افرازی ممکن است یا نه.

ورودی🔗

در سطر اول ورودی، عدد صحیح و مثبت tt که تعداد سناریوها را نشان می‌دهد، داده می‌شود.

1t1000001 \leq t \leq 100 \, 000

در سطر اول هر سناریو، عدد صحیح و مثبت nn آمده که طول رشته را نشان می‌دهد.

1n5000001 \leq n \leq 500 \, 000

در سطر دوم هر سناریو، یک رشته از ارقام 1 تا 9 به نام ss داده می‌شود.

تضمین می‌شود که n1000000\sum n \leq 1000\,000 باشد.

خروجی🔗

در tt سطر برای هر سناریو، در صورتی که می‌توان چنین تقسیمی انجام داده YES و در غیر این صورت NO چاپ کنید.

مثال‌ها🔗

ورودی نمونه ۱🔗

3
3
123
6
123456
11
14323242467
Plain text

خروجی نمونه ۱🔗

YES
NO
YES
Plain text

معادله‌ی سناریو اول به صورت 1+2=31 + 2 = 3 بوده است. بنابراین پاسخ YES می‌شود.

معادله‌ای برای سناریو دوم وجود ندارد

معادله‌ی سناریو سوم به صورت 143+2324=2467143 + 2324 = 2467 بوده است. بنابراین پاسخ YES می‌شود.