#1010 숫자놀이

91  1 s   128 MB  

Description

철수는 얼마 전 ‘나머지’ 연산에 대해 배웠다. 양의 정수 $N$ 을 다른 양의 정수 $M$으로 나눈 나머지는 항상 $0$ 이상 $M − 1$ 이하의 정수가 된다는 사실이 신기한 철수는 혼자만의 숫자 놀이를 고안했다.

먼저 철수는 양의 정수를 $3$개 임의로 고른다: $X_1$,$X_2$,$X_3$ 다음, $3$개의 양의 정수 $P_1$, $P_2$, $P_3$을 고르는데, $P_1 > X_1$, $P_2 > X_2$, $P_3 > X_3$를 만족하도록 고른다. 철수가 알고 싶은 것은 아래의 조건을 만족하는 가장 작은 양의 정수 $N$ 이다:

$N$ 을 $P_1$로 나눈 나머지가 $X_1$, $N$ 을 $P_2$로 나눈 나머지가 $X_2$, $N$ 을 $P_3$으로 나눈 나머지가 $X_3$ 

철수가 선택한 $P_1$, $P_2$, $P_3$, $X_1$, $X_2$, $X_3$가 주어졌을 때, 가장 작은 정수 $N$을 찾는 프로그램을 작성하시오.

Input

첫 행에는 테스트 케이스의 수 $T$ $(1 \leq T \leq 20)$ 가 주어진다.

테스트 케이스로는 공백으로 구분된 정수 $6$개가 순서대로 주어진다. $P_1$, $P_2$, $P_3$, $X_1$, $X_2$, $X_3$ 순서로 주어진다. 각 정수는 $300$을 넘지 않는다.

Output

가장 작은 양의 정수 $N$ 을 출력한다.

단, 조건을 만족하는 $1,000,000,000$미만의 양의 정수가 없을 경우 -1을 출력한다.

Sample Input

Sample Output

3
20 20 20 1 2 3
2 3 5 1 1 1
2 4 8 1 2 3
-1
1
-1

Source

2009 Ajou University Programming Contest