- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
در یک مهمانی \(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\) برابر یک کیک کامل برسد. پس میتوانیم با چهار عملیات هر کیک را به ۱۶ قسمت تقسیم کنیم (هر بار همه قطعات را کنار هم میگذاریم و با یک عملیات همه را نصف میکنیم.) سپس به هر مهمان ۷ قطعه کیک میدهیم.