Cho 8 số nguyên không âm ~𝑑_1~, ~𝑑_2~, … , ~𝑑_4~ và ~𝑟_1~, ~𝑟_2~, … , ~𝑟_4~ trong đó ~∀𝑖~: 0 ≤ ~𝑟_𝑖~ < ~𝑑_𝑖~ Tìm số nguyên dương ~𝑛~ bé nhất thỏa mãn: ~𝑛~ chia ~𝑑_𝑖~ dư đúng ~𝑟_𝑖~ (~∀𝑖~: 1 ≤ ~𝑖~ ≤ 4)

Dữ liệu vào:

• Dòng 1 chứa số ~𝑇~ ≤ ~10^4~ là số test.
• ~T~ 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 ≤ ~𝑟_𝑖~ < ~𝑑_𝑖~ ≤ ~10^4~)

Kết quả: 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.

Ví dụ:

Input:

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

Output:

123
-1