Transforming Pairs

시간 제한2초메모리 제한2048 MB

요약

두 정수와 두 목표가 주어질 때 a+=b 또는 b+=a 연산만으로 최소 연산 횟수를 구하거나 불가능을 판별한다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 그리디
정답자: 아직 제출이 없습니다

문제

Answer $Q$ ( $1\le Q\le 10^5$ ) independent queries each of the following form:

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

입력

The first line contains $Q$ .

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

출력

The answer for each query on a separate line.

예제1

예제 1

입력

예상 출력