Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|
?

EGG - Thả trứng , trò giải trí tuổi teen

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ử .

Được gửi lên bởi:Nguyen Minh Hieu
Ngày:2007-02-25
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:Folklore

hide comments
2017-11-16 04:35:35
1
2 4
test này kq đúng là 2 mà sao bộ test ra 3 nhỉ
2017-01-16 13:41:13
một ngày cày vật vả
đệ quy ->O(n^4)->O(n^3)->O(n^2 log(n))
2016-07-14 12:02:22
O(n^3) ===> O(n^2log(n))
2016-05-28 11:57:05 Nguyễn Vĩnh Thịnh
cái cận làm đpt thành O(m^2 * log m)

Last edit: 2016-05-30 03:57:23
2016-05-08 14:46:49 Ðinh Mai Phương
ai acc cho xin test hiểm đi!
2016-05-06 19:42:23
QHD O(n^3) => TLE ??
2015-05-01 18:50:02 Anh Duc Le
QHĐ O(n^3) có cận =))
2014-10-20 16:04:15 Gao Ðen~Bò Tót Mãnh Lực
1 quả mất 10 lần
2 quả mất 3 lần là sao???
2013-09-18 08:20:08 nguyen quoc huy
minh cung ko biet nua :((
2013-09-18 08:08:27 dương dễ thương vl
tao dth quá hà
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.