Transforming Pairs

문제

Answer $QQ$ ($1\le Q\le {10}^{5}1\backslash le\; Q\backslash le\; 10^5$) independent queries each of the following form:

You are given four integers $a,b,c,da,b,c,d$ ($-{10}^{18}\le a,b,c,d\le {10}^{18}-10^\{18\}\backslash le\; a,b,c,d\backslash le\; 10^\{18\}$). In one operation you can either do $a+=ba\backslash mathrel\{+\}=b$, or $b+=ab\backslash mathrel\{+\}=a$. Determine the minimum number of operations to transform $(a,b)(a,b)$ into $(c,d)(c,d)$, or if it is impossible to do so, output $-1-1$.

입력

The first line contains $QQ$.

The next $QQ$ lines each contain four integers $a,b,c,da,b,c,d$.

출력

The answer for each query on a separate line.