An đang bị phạt và cô giáo đang để một chiếc đồng hồ đếm giây ở cạnh An để tính thời gian phạt. Hiện giờ đồng hồ đang đếm giây. Sau một giây nữa, số chỉ sẽ tăng lên . Tuy nhiên, An biết loại đồng hồ đếm giây này có một lỗ hổng cho phép An làm số chỉ thay đổi ngay lập tức từ thành ở đó là số bé nhất không nhỏ hơn mà chia hết cho . Thời gian thực hiện thao tác làm thay đổi chỉ số này coi như bằng . An sẽ lợi dụng lỗ hổng này để thời gian trôi qua nhanh hơn. Để tránh bị cô giáo phát hiện, An sẽ hack vào lỗ hổng không quá lần. Vậy sau giây nữa, số chỉ lớn nhất của đồng hồ là bao nhiêu?
Ví dụ, và . An có thể ngay lập tức hack để tăng số chỉ lên . Sau giây, đồng hồ chỉ giây, An hack ngay lập tức để đồng hồ chỉ giây. Sau giây nữa, đồng hồ chỉ giây, An hack lần thứ ba để đồng hồ chỉ giây. Vậy sau giây, đồng hồ chỉ giây. Đây là số chỉ lớn nhất có thể đạt được.
Dữ liệu vào:
Dòng đầu tiên chứa số nguyên là số lượng test. Sau đó là test;
Mỗi test gồm một dòng duy nhất chứa bốn số nguyên và .
Dữ liệu ra:
Với mỗi test ghi ra một số nguyên duy nhất là số chỉ lớn nhất trên đồng hồ sau giây trên một dòng.
