Giải bài trực tuyến

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/egg

Tụi trẻ con có được N quả trứng có độ cứng như nhau . Trong giờ ra chơi chúng quyết định thử xem trứng cứng đến mức nào bằng cách thả trứng từ trên tầng cao xuống đất xem ở độ cao nào thì trứng sẽ vỡ . Giả sử độ cứng của trứng là E thì thả trứng ở các tầng từ tầng 1 -> tầng E trứng sẽ không vỡ , và thả trứng bắt đầu ở tầng E + 1 trở đi trứng sẽ vỡ . Cách làm nông dân nhất là ta cứ đem thả từng tầng một từ thấp lên cao đến tầng nào trứng vỡ là biết ngay nhưng mà như thế phải thả nhiều lần quá , giờ ra chơi của bọn trẻ con không được lâu đến thế , hơn nữa tụi nó có tới N quả trứng nên có vỡ 1 số quả cũng chẳng sao , miễn là đạt được mục đích của mình .

Bạn là một lập trình viên siêu hạng , sau khi nghe nỗi niềm của bọn trẻ , bạn có thể giúp gì được bọn trẻ không ? Hay là sẽ chịu thua ? Nếu giải được bài toán hóc búa này thì bạn hãy thử submit xem nào . Biết rằng toà nhà trường học của bọn trẻ có tất cả M tầng ( nếu trứng không vỡ ở tầng M thì có thể coi như nó có độ cứng là M ) .

Chú ý nếu không cẩn thận sẽ rất dễ bị ngộ nhận . Dù làm cách nào đi nữa thì vấn đề muôn thuở vẫn là phải chứng minh được tính đúng đắn của thuật toán .

Input

Dòng 1 : số test T ( 1 ≤ T ≤ 10000 ) .
T dòng tiếp theo mỗi dòng gồm 2 số nguyên N M ( 1 ≤ N , M ≤ 1000 ) .

Output

Với mỗi test ghi ra số lượng lần thả ít nhất ( X ) để có thể xác định được rõ ràng độ cứng của quả trứng ( kể cả trong trường hợp xấu nhất thì với X lần thả cũng có thể xác định được độ cứng của quả trứng ) .

Example

Input:
2
1 10
2 5

Output:
10
3

Giải thích test 1 ( N=1, M=10 ) : Giả sử ta bắt đầu thả trứng ở tầng 5 . Nếu trứng vỡ -> ta không còn trứng để thử nữa ( vì ta có mỗi một quả trứng ) -> không thể xác định được độ cứng của trứng là 0 hay 1, 2, 3, 4 . Nếu ta thả trứng từ tầng 1 , trứng vỡ -> độ cứng của trứng là 0 , nếu không vỡ ta lại thả tiếp ở tầng thứ 2 , … cứ làm như vậy thì ở trường hợp tệ nhất là trứng có độ cứng là 10 thì ta phải mất tới 10 lần thử .