문제
천재 소 Bessie는 새로운 매력, 즉 수학적 마법에 빠지게 되었습니다! 어느 날, 농부 John의 목장 밭을 누비던 중, 그녀는 두 개의 마법에 걸린 건초 더미를 발견합니다. 첫 번째 더미에는 a개의 건초가, 두 번째 더미에는 b개의 건초가 있습니다 (1 ≤ a, b ≤ 10¹⁸). 건초 옆, 흙에 반쯤 묻힌 채로 고대 두루마리가 발견되자, 두루마리를 펼치면 빛나는 글자들이 한 예언을 드러냅니다:
“위대한 초원의 명령을 이행하기 위해서는, 선택받은 자가 이 두 겸손한 건초 더미를 정확히 c개와 d개의 건초로 바꿔놓아야 한다—더도 덜도 아니게.”
Bessie는 오직 다음 두 가지 주문만을 사용할 수 있음을 깨닫습니다:
주문 1: 두 번째 더미에 현재 있는 건초의 수만큼을 첫 번째 더미에 추가하여, 첫 번째 더미의 크기를 늘린다.
주문 2: 첫 번째 더미에 현재 있는 건초의 수만큼을 두 번째 더미에 추가하여, 두 번째 더미의 크기를 늘린다.
이 주문들은 순차적으로 실행해야 하며, 원하는 만큼, 임의의 순서로 사용할 수 있습니다. 최종적으로 첫 번째 더미가 정확히 c개의 건초, 두 번째 더미가 정확히 d개의 건초가 되어야 합니다 (1 ≤ c, d ≤ 10¹⁸).
각각 T (1 ≤ T ≤ 10⁴)개의 독립 테스트 케이스에 대해, 예언을 이행하기 위해 필요한 최소 주문(연산) 횟수를 구하거나, 불가능할 경우 -1을 출력하세요.
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어집니다.
이후 T개의 줄 각각에 네 정수 a, b, c, d가 공백으로 구분되어 주어집니다.
출력
각 테스트 케이스마다, 예언을 이행하기 위해 필요한 최소 주문(연산) 횟수를 한 줄에 출력하세요. 만약 목표 상태에 도달하는 것이 불가능하다면 -1을 출력합니다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | |
| #2 | 30점 | T ≤ 10 및 a, b, c, d ≤ 10⁶ |
| #3 | 50점 | 추가 제약 없음 |
예제1
4
5 3 5 2
5 3 8 19
5 3 19 8
5 3 5 3
-1
3
-1
0
첫 번째 테스트 케이스: a=5, b=3, c=5, d=2 인 경우, b가 이미 d보다 크므로 두 번째 더미를 줄일 수 없으며, 연산은 오직 건초를 늘리는 방향으로만 가능하기 때문에 목표에 도달할 수 없습니다.
두 번째 테스트 케이스: a=5, b=3, c=8, d=19 인 경우, Bessie는 먼저 주문 1을 사용하여 첫 번째 더미를 5에서 8로 만들고 (즉, (5,3) → (8,3)), 이후 주문 2를 두 번 사용하여 두 번째 더미를 3에서 11, 그리고 19로 만들 수 있습니다. 총 3번의 연산이 필요합니다.
세 번째 테스트 케이스: a=5, b=3, c=19, d=8 인 경우, 목표인 c와 d의 순서가 바뀌어 있어 연산으로 만들 수 없습니다.
네 번째 테스트 케이스: a=5, b=3, c=5, d=3 인 경우, 이미 목표 상태에 도달해 있으므로 추가 연산이 필요 없습니다.
예제2
1
1 1 1 1000000000000000000
999999999999999999
단일 테스트 케이스에서 초기 상태는 (1, 1)이고 목표는 (1, 10¹⁸)입니다. 첫 번째 더미는 이미 목표치에 도달해 있으므로, 두 번째 더미를 1에서 10¹⁸으로 만들기 위해 10¹⁸ - 1번의 연산이 필요합니다.