분수 줄이기

Chiaki에게 분수 $\frac{a}{b}$가 있다. 이 분수는 기약분수가 아니어도 된다. Chiaki는 다음 두 연산을 할 수 있다.

• 현재 분수가 $x$일 때, $-\frac{1}{x}$로 바꿀 수 있다.
• 현재 분수가 $x$일 때, $x+1$로 바꿀 수 있다.

Chiaki는 $\frac{a}{b}$를 $0$으로 만들기 위해 필요한 최소 연산 횟수를 알고 싶어 한다. 이 수는 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 구한다.

여러 개의 테스트 케이스가 주어진다. 입력의 첫째 줄에는 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10^5$) 각 테스트 케이스는 다음과 같다.

첫째 줄에 두 정수 $a$와 $b$가 주어진다. ($-10^{18} \le a \le 10^{18}, 1 \le b \le 10^{18}$) 이는 분수를 나타낸다.

각 테스트 케이스마다 $\frac{a}{b}$를 $0$으로 만들기 위한 최소 연산 횟수를 $10^9+7$로 나눈 나머지를 출력한다. $0$으로 만들 수 없다면 $-1$을 출력한다.

1번째 예제에서는 연산이 필요하지 않다.

2번째 예제에서 가능한 수열의 한 예는 $\frac{1}{1} \to -\frac{1}{1} \to 0$이다.

3번째 예제에서 가능한 수열의 한 예는 $-\frac{1}{2} \to \frac{1}{2} \to -\frac{2}{1} \to -\frac{1}{1} \to 0$이다.

4번째 예제에서 가능한 수열의 한 예는 $-\frac{2}{4} \to \frac{2}{4} \to -\frac{4}{2} \to -\frac{2}{2} \to 0$이다.

5번째 예제에서 가능한 수열의 한 예는 $\frac{8}{5} \to -\frac{5}{8} \to \frac{3}{8} \to -\frac{8}{3} \to -\frac{5}{3} \to -\frac{2}{3} \to \frac{1}{3} \to -\frac{3}{1} \to -\frac{2}{1} \to -\frac{1}{1} \to 0$이다.