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

---

درخت دودویی از کسرها داریم که روی هر راسش کسری به فرم \(\frac {a_i} {b_i}\) نوشته شده است. درخت به این شکل ساخته می‌شود:

1. \(a_{1}\) = \(b_{1}\) = \(1\)
2. \(a_{2i}\) = (\(a_{i}\) + \(b_{i}\) ) , \(b_{2i}\) = \(b_{i}\) (بچه سمت چپ)
3. \(a_{2i+1}\) = \(a_{i}\) , \(b_{2i+1}\) = (\(a_{i}\) + \(b_{i}\) ) (بچه سمت راست)

فاصله دو راس در درخت را تعداد یال‌های تنهای مسیر بینشان تعریف می‌کنیم.

به شما \(Q\) درخواست که هر کدام شامل کسری به فرم \(\frac {p_i} {q_i}\) داده می‌شود.

برای هر عدد موجود در درخواست‌ها، اگر تنها یک راس در درخت وجود داشت که کسرش برابر کسر ورودی داده شده بود، فاصله راس آن کسر تا راس ۱ را در خروجی چاپ کنید و در غیر این صورت \(-1\) خروجی دهید.

ورودی

در خط اول \(Q\) و در \(Q\) خط بعدی\(p_{i}\) و \(q_{i}\) به شما داده شده.

\[1 \le Q \le 100\ 000\]

\[1 \le p_{i},q_{i} \le 10^{18}\]

خروجی

در خط \(i\)ام اگر کسری معادل عدد \(\frac {p_i} {q_i}\) بود و فقط این کسر معادل این عدد بود فاصله‌ی آن را از راس ۱ خروجی دهید در غیر این صورت \(-1\) خروجی دهید.

مثال

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

2
1 2
3 5

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

1
3