Hàng đợi trà

Có $n$ học sinh xếp hàng lấy trà từ một ấm trà duy nhất. Học sinh thứ $i$ đến cuối hàng vào đầu giây thứ $l_i$. Nếu có nhiều học sinh đến cùng một giây, học sinh có chỉ số nhỏ hơn đứng trước.

Mỗi học sinh khi đến lượt sẽ dùng ấm trà đúng $1$ giây rồi rời hàng. Nếu đến đầu giây $r_i$ mà học sinh $i$ vẫn chưa lấy được trà (tức vẫn còn người trước mình), học sinh đó sẽ bỏ về tay không.

Với mỗi học sinh, hãy xác định giây mà học sinh đó lấy được trà, hoặc $0$ nếu học sinh bỏ về.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số test ($1\le t\le 1000$).
• Mỗi test bắt đầu bằng một dòng chứa $n$ — số học sinh ($1\le n\le 1000$).
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $l_i,r_i$ ($1\le l_i\le r_i\le 5000$). Đảm bảo $l_{i-1}\le l_i$ với mọi $i\ge 2$.

Tổng $n$ trên tất cả các test không vượt quá $1000$.

Dữ liệu ra

Với mỗi test, in ra trên một dòng $n$ số nguyên, số thứ $i$ là giây mà học sinh $i$ lấy được trà, hoặc $0$ nếu bỏ về.

Ví dụ