Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Halley nhận nhiệm vụ điều chế vắc xin tiêu diệt Covid19. Trong quá trình nghiên cứu trong phòng thí nghiệm, cậu điều chế ra a loại vắc xin. Để thử nghiệm a loại vắc xin này, cậu trích xuất b lượng virus ban đầu từ người bệnh. Biết rằng ta tiêu diệt được hết lượng virus này khi và chỉ khi lượng virus hiện tại bằng 0. Halley nhận ra rằng khi dùng loại vắc xin thứ i cậu sẽ tiêu diệt  d_i lượng virus nhưng nếu còn ít nhất một lượng virus nào đó, số lượng virus sẽ lại tăng thêm h_i lượng. Nếu không thể tiêu diệt được hết, chắc lại phải tiếp tục thực hiện cách ly xã hội thôi!

Halley không biết số lượng vắc xin ít nhất để dùng tiêu diệt toàn bộ virus, nhưng vừa hay cậu quen một bạn bên CLB ITPTIT có thể lập trình chương trình tính toán cho bài toán này.

Còn bạn thì sao ? Hãy thử sức lập trình chương trình đó xem nhé.

Input

Dòng đầu tiên gồm số nguyên t (1 <= t <= 1000 ) là số truy vấn.

Dòng đầu tiên của mỗi truy vấn gồm hai số nguyên a và b (1 <= a <= 100, 1<=  b <= 10^12) là số loại vắc xin và số lượng virus ban đầu.

a dòng tiếp theo của mỗi truy vấn là loại vắc xin bạn có. Dòng thứ i gồm hai số nguyên d_i và h_i  (1 <= d_i, h_i <= 10^9)  mô tả đặc điểm của loại vắc xin đó.

Output

Với mỗi truy vấn in ra số vắc xin bạn cần dùng để tiêu diệt virus.

Nếu không thể tiêu diệt virus in ra “Social Quarantine”.

Example

Giải thích

Trường hợp này Halley chỉ cần dùng 3 lần loại vắc xin đầu tiên là có thể tiêu diệt được virus.

Lượng virus còn lại sau lần 1: 10 – 4 + 1 = 7

Lượng virus còn lại sau lần 2: 7 – 4 + 1 = 4

Lượng virus còn lại sau lần 3: 4 – 4 = 0