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