Cho 8 số nguyên không âm \(𝑑_1, 𝑑_2, … , 𝑑_4\) và \(𝑟_1, 𝑟_2, … , 𝑟_4\) trong đó \(∀𝑖: 0 \le 𝑟_𝑖 < 𝑑_𝑖\)

Tìm số nguyên dương \(𝑛\) bé nhất thỏa mãn: \(𝑛\) chia \(𝑑_𝑖\) dư đúng \(𝑟_𝑖\) (\(∀𝑖: 1 \le 𝑖 \le 4\))

Input

• Dòng 1 chứa số \(𝑇 \le 10^4\) là số test.
• \(𝑇\) khối dòng tiếp theo mỗi khối 4 dòng chứa dữ liệu cho 1 test: Dòng thứ \(𝑖\) chứa cặp số nguyên \(𝑑_𝑖\), \(𝑟_𝑖\) cách nhau bởi dấu cách (\(0 \le 𝑟_𝑖 < 𝑑_𝑖 \le 10^4\))

Output

• Với mỗi test ghi ra một số nguyên dương duy nhất là số \(𝑛\) tìm được, trong trường hợp không tồn tại số \(𝑛\) thỏa mãn điều kiện, ghi ra số \(-1\)

Example

2
20 3
15 3
21 18
35 18
5 1
5 2
5 3
5 4

123
-1