- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در یک مهمانی $n$ عدد کیک با اندازه برابر داریم. $k$ مهمان به این مهمانی می‌آیند و میزبان می‌خواهد کیک‌ها را طوری تقسیم کند که به هر مهمان مقدار برابری کیک برسد و هیچ کیکی باقی نماند.
روش تقسیم کیک‌ها به این صورت است که در هر مرحله میزبان تعداد دلخواهی قطعه کیک را انتخاب می‌کند و همه را به دو قسمت برابر تقسیم می‌کند.
از آن‌جا که میزبان سرش حسابی شلوغ است از شما خواسته است که در تقسیم کیک‌ها را به او کمک کنید و به او بگویید که اصلا این کار امکان‌پذیر است یا خیر و اگر امکان‌پذیر هست حداقل چند مرحله تقسیم باید انجام شود.
ورودی
در خط اول ورودی ابتدا عدد $t$ که نشان‌دهنده‌ی تعداد مهمانی‌های برگزار شده، آمده‌است.
$$1 \le t \le 100 , 000$$
سپس در $t$ خط بعدی، در هر خط دو عدد $n$ و $k$ به ترتیب داده می‌شوند که اولی نشان‌دهنده‌ی تعداد کیک‌های اولیه و دومی تعداد مهمان‌ها است. $$1 \le n, k \le 10^9$$
خروجی
برای هر مهمانی اگر تقسیم کیک امکان‌پذیر بود، کم‌ترین تعداد برش لازم و در غیر این صورت عدد -1 را در یک خط به عنوان خروجی چاپ کنید.
مثال
ورودی نمونه ۱
3
10 3
4 8
7 16
خروجی نمونه ۱
-1
1
4
سناریو اول. در سناریو اول $n = 10$ کیک و $k = 3$ مهمان داریم. پس باید به هر مهمان اندازه‌ی $\frac{10}{3} = 3.333\cdots$ برابر یک کیک کامل برسد. هر بار می‌توانیم فقط قطعات کیک را نصف کنیم پس هیچ وقت نمی‌توانیم با تعدادی برش و برداشتن چند قطعه به این عدد برسیم.
سناریو دوم. در سناریو اول $n = 4$ کیک و $k = 8$ مهمان داریم. پس باید به هر مهمان اندازه‌ی $\frac{4}{8} = 0.5$ برابر یک کیک کامل برسد. پس می‌توانیم با یک عملیات همه‌ی کیک‌ها را نصف کنیم و به هر مهمان یک قطعه بدهیم.
سناریو سوم. در سناریو اول $n = 7$ کیک و $k = 16$ مهمان داریم. پس باید به هر مهمان اندازه‌ی $\frac{7}{16} = 0.4375$ برابر یک کیک کامل برسد. پس می‌توانیم با چهار عملیات هر کیک را به ۱۶ قسمت تقسیم کنیم (هر بار همه قطعات را کنار هم می‌گذاریم و با یک عملیات همه را نصف می‌کنیم.) سپس به هر مهمان ۷ قطعه کیک می‌دهیم.
ارسال پاسخ برای این سؤال