محدودیت زمانی: 1ثانیه

محدودیت سورس برنامه: 1024کیلوبایت

محدودیت حافظه: 256مگابایت


رضا رشته ها را دوست دارد و از ریاضیات متنفر  است. بالعکس دوستش حسین از ریاضیات خوشش می آید و از رشته ها متنفر است.

معلم آن ها می خواهد از آنها امتحانی بگیرد که شامل هردوی این سرفصل های درسی برنامه نویسی باشد، پس معلمشان به آن ها یک رشته می دهد، رشته ای که شامل اعداد 0 تا 9 است. سپس معلم از آن ها می پرسد که آیا می توانند رشته را به Kقسمت تقسیم کند که از مقدار ثابت Z بزرگتر نباشد. معلم از آن ها می خواهد در حالتی که جمع قسمت ها بیشترین باشد، جمع قسمت ها را چاپ کند.

خب آنها چون نمی توانند این کار را بکنند از شما کمک خواسته اند.

اگر جوابی برای Kقسمت، با شرط خواسته شده وجود نداشت، در خروجی -1 را چاپ کنید.


ورودی:

اولین خط شامل T، تعداد تست هاست. (عددی بین 1 تا 10)

سپس در اولین خط هر ورودی دو عدد K و Z می آیند. (K عددی بین 1 تا 100 و Z عددی بین 1 تا 10 به توان 9)

در خط دوم هر ورودی هم رشته ای می آید که حداکثر 100کاراکتر دارد.


خروجی:

در T خط جواب هر تست را بدهد.


ورودی مثال:

2
1 6
30901
2 85
07565

خروجی مثال:

-1
140


لینک جاج: https://www.hackerearth.com/tavisca-hiring-challenge-1/algorithm/string-partition/

*برای دسترسی به ارسال پاسخ باید در سایت Hackerearth ثبت نام و حتما لاگین باشید.

*در پایین صفحه پس از توضیح سوال ادیتور مربوطه وجود دارد از کادر سمت چپ گزینه ی آپلود فایل python 3 را انتخاب کنید و سپس به یکی از روش های آپلود فایل یا نوشتن مستقیم برنامه در ادیتور برنامه تان را submit کنید.