+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------------- درخت دودویی از کسرها داریم که روی هر راسش کسری به فرم $\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 ```