시간 제한메모리 제한제출정답맞은 사람정답 비율
3 초 512 MB108321938.000%

문제

방학을 맞은 귀여운 백남이는 여행을 떠날 준비를 하고 있다.

여행 준비를 하기 앞서, 백남이는 필수품들을 구매하기 위해 저금통을 깨서 자금을 충당하려고 한다. 저금통에서 많은 금화를 얻게 된 백남이는 금화의 개수가 궁금해졌다.

MBTI가 T(사고형)인 백남이는 사고력 증진을 위해 금화의 개수를 특이하게 구하고 싶어졌다.

백남이가 금화의 개수를 구하는 법은 다음과 같다.

특별한 상자 3개를 준비한다. 각각의 상자에는 수가 각인되어 있는 데, 해당 수는 $A$, $B$, $C$ 이다. 해당 상자에 물건을 넣으면 물건의 개수에서 각인된 수를 나눴을 때의 나머지를 알 수 있게 된다. 금화를 상자에 넣어 나온 수를 각각 $a$, $b$, $c$ 라고 할 때, 백남이가 가지고 있는 금화의 개수를 구해주자.


 

입력

첫째 줄에 테스트 케이스의 개수 $T$ 가 주어진다. ($1 \le T \le 1,000,000$)

각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 여섯 개의 정수 $A$, $B$, $C$, $a$, $b$, $c$ 가 주어진다.

($1 \le A,\;B,\;C\le1,000,000$) ($0 \le a < A$) ($0 \le b < B$) ($0 \le c < C$)

출력

각 테스트 케이스 마다 금화의 개수를 출력한다. 만약 가능한 금화의 개수가 여러개라면 가장 작은 값을 출력한다.

만일 주어진 정수에 대한 해가 존재하지 않는다면, -1 을 출력한다.

예제 입력 1

4
4 3 2 0 2 0
8 4 2 4 2 1
19 52 25 7 50 2
14 23 51 13 22 50

예제 출력 1

8
-1
102
16421

출처

University > 충남대학교 > 제5회 생각하는 프로그래밍 대회  H번