Problem Statement

You are given pairs of non-negative integers $a = (a_1,a_2)$ and $b = (b_1,b_2)$. You can perform the following operation on the pair $a$ any number of times, possibly zero.

• Operation: Choose a positive real number $x$. Replace $a = (a_1,a_2)$ with $(\lfloor a_1x\rfloor, \lfloor a_2x\rfloor)$.

Your objective is to make the pair $a$ equal the pair $b$. Determine whether it is achievable. If it is, find the minimum number of times you must perform the operation to achieve it.

You have $T$ test cases to solve.

Constraints

• $1\leq T\leq 10^5$
• $0\leq a_1, a_2, b_1, b_2 \leq 10^9$

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each test case is given in the following format:

a_1 a_2 b_1 b_2

Output

Print $T$ lines. The $i$-th line should contain -1 if it is impossible to make $a$ equal $b$ in the $i$-th test case, and otherwise, the minimum number of times the operation must be performed to achieve the objective.