천재 소 Bessie는 새로운 매력, 즉 수학적 마법에 빠지게 되었습니다! 어느 날, 농부 John의 목장 밭을 누비던 중, 그녀는 두 개의 마법에 걸린 건초 더미를 발견합니다. 첫 번째 더미에는 a개의 건초가, 두 번째 더미에는 b개의 건초가 있습니다 (1 ≤ a, b ≤ 10¹⁸). 건초 옆, 흙에 반쯤 묻힌 채로 고대 두루마리가 발견되자, 두루마리를 펼치면 빛나는 글자들이 한 예언을 드러냅니다:

“위대한 초원의 명령을 이행하기 위해서는, 선택받은 자가 이 두 겸손한 건초 더미를 정확히 c개와 d개의 건초로 바꿔놓아야 한다—더도 덜도 아니게.”

Bessie는 오직 다음 두 가지 주문만을 사용할 수 있음을 깨닫습니다:

주문 1: 두 번째 더미에 현재 있는 건초의 수만큼을 첫 번째 더미에 추가하여, 첫 번째 더미의 크기를 늘린다.
주문 2: 첫 번째 더미에 현재 있는 건초의 수만큼을 두 번째 더미에 추가하여, 두 번째 더미의 크기를 늘린다.

이 주문들은 순차적으로 실행해야 하며, 원하는 만큼, 임의의 순서로 사용할 수 있습니다. 최종적으로 첫 번째 더미가 정확히 c개의 건초, 두 번째 더미가 정확히 d개의 건초가 되어야 합니다 (1 ≤ c, d ≤ 10¹⁸).

각각 T (1 ≤ T ≤ 10⁴)개의 독립 테스트 케이스에 대해, 예언을 이행하기 위해 필요한 최소 주문(연산) 횟수를 구하거나, 불가능할 경우 -1을 출력하세요.

#8313 upload 1 done 1 how_to_reg 1 call_split Subtarea

Transforming Pairs timer 1s memory 1024MB

#8313
Subtarea

Transforming Pairs 1s 1024MB