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

درخت دودویی از کسرها داریم که روی هر راسش کسری به فرم $\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