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