- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
درخت دودویی از کسرها داریم که روی هر راسش کسری به فرم \(\frac {a_i} {b_i}\) نوشته شده است. درخت به این شکل ساخته میشود:
- \(a_{1}\) = \(b_{1}\) = \(1\)
- \(a_{2i}\) = (\(a_{i}\) + \(b_{i}\) ) , \(b_{2i}\) = \(b_{i}\) (بچه سمت چپ)
- \(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