P22280 [HackerEarth] The National Egg Co-ordination Committee (NECC) has been able to come up with a few variants of chicken egg that is stronger than the naturally available egg. To demonstrate the strength
普及-
题目描述

The National Egg Co-ordination Committee (NECC) has been able to come up with a few variants of chicken egg that is stronger than the naturally available egg. To demonstrate the strength of eggs, they have decided to conduct a drop test. To characterize the strength, they will pick a few buildings and find the minimum floor from which any of the eggs break. Then, they would be able to represent the strength in terms of the building and its floors. However strange, this method is expected to bring the much needed attention to the egg-breaking problem and the solution obtained through Genetic Engineering.

NECC, however, wants to minimize the number of eggs that break. But they are lazy people, so they wouldn't drop the egg from each floor to test if it breaks. They have asked you to tell them the minimum number of drops required to ascertain the floor from which when a particular kind of egg is dropped, it breaks, given that they have 'k' eggs of that type and there are 'n' floors in the building.

INPUT FORMAT
First line contains a single positive integer, T ≤ 1000, which indicates the number of test cases that follow. The next T lines contain 2 positive integers, N ( ≤ 500) and K ( ≤ 500), which are the number of floors and eggs respectively.

OUTPUT FORMAT
For every pair of floors and eggs, output a single number which is equal to the minimum number of trials that would be required to find the floor from which the egg breaks, in the worst-case.

SAMPLE INPUT
4
10 1
10 2
36 2
100 2

SAMPLE OUTPUT
10
4
8
14

输入格式

见题面

输出格式

见题面

样例输入
1000 67 394 416 179 60 192 245 444 327 495 280 174 253 201 58 41 204 395 51 401 319 113 8 443 211 97 5 214 411 293 383 342 367 448 217 237 195 55 287 493 219 499 491 23 98 380 215 332 412 490 251 454 493 299 174 54 56 356 125 490 467 121 161 378 348 146 151 350 306 239 60 497 304 498 16 283 278 147 455 486 426 99 52 321 397 487 401 127 457 369 51 48 472 434 358 276 412 366 117 440 191 211 230 423 169 18 289 183 193 231 322 424 67 93 41 308 462 267 325 105 464 8 22 31 12 159 42 87 46 491 453 394 259 481 312 152 148 153 445 53 338 147 407 244 225 479 131 229 85 468 350 73 423 362 215 172 35 480 23 465 127 455 190 494 381 171 288 323 52 400 256 299 477 239 21 304 432 188 45 493 473 324 227 285 414 429 355 342 395 286 178 319 202 381 196 134 417 142 90 344 279 138 193 21 449 457 63 175 168 121 393 451 306 193 346 286 420 258 480 117 260 336 478 369 212 42 426 210 14 29 344 41 233 400 190 210 266 217 192 272 489 270 482 377 130 314 210 22 36 114 29 139 422 42 446 304 288 481 89 490 439 42 434 480 256 36 34 97 246 299 180 338 110 490 402 303 312 228 231 287 207 3 300 446 31 12 247 423 20 335 250 456 426 350 352 271 99 329 408 46 246 117 266 66 174 59 348 46 480 295 151 90 266 436 303 234 380 229 436 202 79 475 376 432 387 42 42 413 293 349 86 399 165 352 116 255 199 149 343 102 76 368 49 114 71 232 257 67 133 6 383 164 238 469 27 417 450 109 440 355 246 189 247 139 468 230 83 79 95 170 187 183 373 269 451 302 233 377 203 173 432 135 376 32 275 470 292 23 371 494 143 15 39 472 91 46 30 62 41 117 182 271 317 209 292 118 327 480 253 53 214 195 451 61 237 278 333 143 216 131 330 373 126 444 294 387 483 284 364 396 491 421 17 494 413 92 327 355 68 100 413 440 384 351 101 114 313 143 499 75 437 478 373 409 352 58 144 87 70 258 492 241 27 499 325 330 296 109 444 34 201 131 388 164 442 397 395 332 312 466 459 426 256 375 328 407 450 483 188 327 75 470 43 378 284 376 31 110 429 293 449 190 82 276 231 282 59 227 109 350 385 461 328 176 480 396 86 405 114 230 192 105 267 407 348 437 286 77 218 362 389 134 19 459 298 235 163 94 333 283 129 365 406 458 474 45 345 435 42 316 437 177 44 200 170 184 329 219 455 55 137 254 275 176 11 83 475 226 158 206 136 148 374 388 323 357 279 366 292 364 423 196 150 236 25 14 260 370 59 13 302 238 250 298 408 428 320 307 400 61 223 154 37 118 390 122 262 122 288 127 212 407 423 339 391 478 379 157 434 147 32 130 53 129 365 353 126 393 111 100 481 297 35 227 383 294 74 65 122 38 265 358 215 321 120 21 295 189 323 110 201 338 262 176 481 335 40 85 182 304 235 426 79 19 116 218 354 297 146 297 61 36 138 97 274 8 491 305 458 104 395 492 246 137 40 160 164 490 158 42 454 97 10 340 481 169 308 277 442 84 482 181 261 353 58 235 242 301 344 117 490 340 327 83 340 495 37 97 275 268 286 193 180 202 51 385 294 209 69 290 349 250 285 93 249 400 226 335 228 118 95 360 67 331 382 428 79 282 6 189 36 162 113 281 446 469 153 237 97 348 407 386 482 229 133 460 354 46 111 437 81 333 219 373 400 84 71 82 208 52 411 347 464 477 31 250 390 364 4 42 445 382 433 306 184 18 391 74 275 14 302 237 388 459 249 476 136 95 471 147 22 120 415 22 149 445 495 103 472 163 109 489 48 271 198 467 184 495 355 241 251 43 193 413 42 126 392 446 443 104 468 59 370 362 262 183 196 105 131 81 8 463 346 151 244 429 191 21 147 159 67 160 388 356 40 367 35 468 240 361 420 173 373 219 64 280 403 257 291 137 8 14 212 236 178 317 154 17 449 408 360 451 296 364 332 66 105 437 421 280 490 272 434 273 138 410 435 459 23 161 277 407 275 129 14 389 244 467 466 9 304 356 132 454 38 117 288 266 218 454 116 456 223 140 51 217 329 112 108 172 160 337 93 227 83 427 182 459 274 125 424 463 308 157 377 126 201 460 237 76 131 83 7 365 96 337 203 451 337 251 72 100 412 14 488 331 55 97 305 230 237 175 246 135 430 362 306 160 8 160 225 451 380 420 95 139 208 389 22 341 386 248 428 304 354 449 273 47 368 237 231 180 307 374 339 467 39 307 339 441 108 388 182 216 156 393 6 419 487 487 169 81 189 213 334 178 85 145 333 242 163 123 19 425 416 295 499 210 151 459 300 379 136 297 285 322 400 141 437 283 98 272 419 115 367 386 430 360 32 115 194 413 27 214 231 52 356 240 91 59 426 454 121 389 334 145 374 344 410 492 369 250 439 100 85 405 294 6 493 152 266 332 413 68 494 70 309 409 107 161 255 355 324 302 331 318 66 126 299 262 373 170 463 353 204 285 471 267 81 315 94 473 164 396 99 146 290 485 5 420 414 191 271 309 243 239 284 117 92 378 128 449 445 370 90 264 487 454 286 220 222 392 97 188 216 184 146 331 154 74 221 361 467 292 106 113 213 426 17 459 14 89 259 129 349 225 124 308 466 483 201 192 407 113 130 399 214 425 247 225 382 422 199 149 303 111 327 8 187 270 175 260 406 454 287 161 281 18 273 171 6 403 426 386 44 316 219 21 421 186 365 352 252 129 369 403 390 19 253 152 419 178 448 181 391 234 372 338 465 230 248 283 315 383 271 157 429 58 370 63 120 487 89 216 319 362 461 14 33 382 26 363 95 76 54 44 330 191 316 280 483 441 194 207 199 24 372 277 412 163 239 149 153 216 485 139 445 369 197 100 58 307 262 149 187 12 375 126 500 182 203 449 330 400 187 377 275 48 160 257 43 420 490 232 456 431 330 310 206 3 380 106 456 58 100 150 419 276 312 432 214 452 409 457 49 219 237 101 131 389 89 136 52 117 274 204 351 125 127 334 14 375 438 89 52 348 477 466 76 5 373 5 470 368 379 275 100 16 54 96 425 170 485 272 144 213 153 381 174 347 250 188 102 495 80 43 74 415 480 147 132 72 239 223 331 14 233 397 417 224 479 79 491 410 354 42 108 140 151 422 80 461 49 499 405 391 54 195 186 106 172 229 252 159 426 129 279 379 492 244 472 362 482 254 28 210 198 18 278 301 66 207 310 245 275 299 102 417 500 382 137 480 80 144 347 29 136 159 307 345 378 274 163 44 254 256 496 315 162 500 300 108 8 439 81 70 396 62 164 428 95 361 212 219 395 165 392 477 167 75 157 238 294 446 380 112 121 170 468 364 339 326 138 445 382 475 97 457 451 370 38 124 98 35 268 272 155 312 41 355 68 255 181 227 429 235 105 239 23 319 41 283 239 394 173 91 118 273 354 431 108 206 355 304 277 77 492 221 349 184 385 384 243 387 140 496 434 99 212 14 79 459 64 247 209 272 418 303 182 311 384 157 469 68 141 335 53 444 207 22 22 337 217 79 319 470 116 440 457 453 174 454 326 401 325 303 242 83 259 416 355 115 218 101 487 251 388 385 31 331 229 500 431 294 249 191 321 109 14 494 71 236 22 330 220 256 431 13 471 248 182 428 258 285 21 237 201 347 138 230 54 202 441 23 11 312 23 210 178 11 133 17 217 138 412 189 150 46 359 414 126 294 368 251 275 457 434 241 400 280 449 28 129 402 468 482 87 275 350 161 224 160 23 485 201 199 293 144 308 405 194 52 329 251 339 478 119 203 237 245 127 318 148 182 385 111 13 410 370 258 104 359 9 109 86 348 94 237 376 318 120 195 223 416 474 8 439 233 318 183 447 328 5 100 155 338 179 104 126 156 6 309 468 351 26 41 381 454 87 453 141 374 43 487 449 329 185 180 66 389 427 43 419 430 438 68 388 450 234 44 400 183 25 9 18 451 200 392 272 62 44 137 54 328 247 73 66 82 81 491 133 474 8 397 189 87 141 187 443 101 175 353 198 149 24 425 463 298 196 5 227 242 126 236 142 137 155 111 336 116 168 360 185 324 452 68 252 312 51 494 343 409 121 63 278 478 407 325 119 154 212 328 357 278 52 288 204 346 438 271 219 308 138 149 423 481 232 233 9 445 257 195 237 101 435 166 55 393 334 489 105 195 126 345 343 261 72 134 165 169 274 269 367 365 233 261 350 336 134 407 446 101 82 250 487 474 291 11 295 64 496 411 335 429 275 113 182 352 91 279 114 355 106 427 464 488 349 3 134 427 27 287 353 114 427 12 463 417 171 431 108 430 370 404 190 491 111 38 204 214 190 176 105 322 236 490 81 358 264 461 209 6 356 69 125 497 112 177 149 35 365 113 420 366 324 86 293 306 417 109 286 457 402 450 468 398 32 109 475 220 169 311 351 322 49 305 315 128 230 225
样例输出
7 9 6 8 9 9 8 6 8 6 9 4 8 3 9 9 9 8 8 9 8 9 7 8 9 8 9 8 6 7 9 8 9 8 9 6 9 5 9 9 9 6 9 9 9 6 9 9 9 7 8 8 8 9 8 9 7 6 9 9 9 5 4 6 6 9 9 9 8 9 9 9 8 8 7 9 9 8 6 5 7 8 9 9 6 9 9 5 9 6 9 8 9 9 9 8 8 8 9 7 9 8 9 6 8 9 9 9 9 9 9 9 8 9 4 9 8 8 9 8 9 9 8 8 6 5 9 9 9 7 9 9 9 6 8 8 7 9 9 8 11 9 5 8 5 8 9 9 7 9 8 9 8 9 9 8 9 9 9 9 7 9 9 6 9 7 8 7 8 9 7 6 7 9 8 9 8 5 9 9 8 8 9 7 7 8 9 9 8 8 9 9 9 9 9 8 6 7 5 6 8 9 9 9 8 8 9 8 9 8 9 7 9 9 9 9 5 9 9 7 9 9 7 9 9 9 9 9 8 7 9 5 9 9 9 8 9 9 9 9 9 9 9 9 8 7 6 9 5 9 9 7 8 6 7 9 9 9 7 7 8 9 9 9 8 9 5 9 8 9 8 9 9 9 6 9 6 8 9 9 8 9 4 9 8 8 9 9 9 9 9 8 5 9 6 9 8 9 9 9 8 6 9 9 9 8 9 9 9 9 6 6 9 7 7 9 6 9 7 7 9 8 7 9 9 8 9 9 6 8 8 7 7 9 8 6 8 9 9 9 9 8 6 8 8 9 4 9 9 9 9 9 6 8 9 9 9 9 6 9 9 8 6 9 7 9 9 8 8 8 7 7 9 7 3 6 7 9 8 7 9 9 8 9 7 7 8 9 7 8 9 9 5 9 3 9 9 8 9 9 9 9 8 8 9 5 9 8 9 9 7 6 8 8 9 8 8 6 9 9 9 9 9 8 8 4 9 8 8 8 7 9 6 6 8 9 9 7 9 9 4 8 8 8 9 9 9 9 7 9 9 9 8 9 5 9 9 4 8 9 9 8 6 9 8 7 8 6 9 7 8 7 7 8 9 9 9 9 8 8 8 3 7 8 9 7 9 9 6 9 8 8 9 9 4 8 9 7 8 5 9 9 9 9 9 8 9 9 6 9 7 8 8 3 9 8 8 9 7 9 8 5 9 9 8 9 8 9 9 9 7 9 9 9 6 8 5 8 9 7 9 7 9 9 9 9 9 7 9 9 9 9 9 9 7 8 9 9 7 9 9 9 8 9 7 7 8 7 9 3 9 9 8 9 7 8 9 7 9 9 8 7 8 8 8 8 9 7 8 5 4 9 9 7 9 8 9 8 8 8 9 8 9 9 8 8 9 9 9 9 3 9 6 8 9 9 8 9 9 8 9 9 9 9 9 8 9 9 9 9 7 7 9 9 6 5 7 6 9 9 9 8 8 9 9 8 8 9 9 8 6 9 8 9 9 8 9 8 9 8 6 9 9 9 11 9 9 7 9 9 8 9 6 8 8 7 6 9 9 7 4 9 6 9 7 9 9 9 7 6 9 9 8 8 8 8 7 7 7 9 8 8 9 8 9 9 9 9 7 8 7 6 9 6 8 8 8 9 9 9 9 9 5 8 9 7 9 9 7 9 8 7 9 8 9 9 8 8 9 8 9 4 7 9 8 7 8 9 9 8 8 9 9 7 9 9 8 9 7 9 6 7 9 8 6 7 8 9 7 5 6 8 8 7 9 7 9 9 9 9 9 8 8 9 8 7 7 8 9 8 9 9 8 6 8 5 8 9 7 9 8 9 9 8 9 9 8 9 9 5 8 9 8 9 4 7 5 8 9 9 8 9 5 8 8 6 9 4 5 8 8 8 9 8 9 7 9 9 9 9 9 8 9 7 9 8 5 8 9 9 8 9 9 7 8 7 8 9 4 9 7 4 7 7 9 7 8 9 9 9 9 3 8 8 7 3 9 5 9 7 8 6 9 8 7 9 9 9 9 8 9 5 5 8 9 6 6 8 7 7 8 4 8 8 9 8 8 5 9 8 8 7 8 8 9 8 8 9 8 6 9 7 9 9 7 8 9 6 8 9 8 8 9 8 4 9 8 9 6 9 7 7 9 7 8 9 9 8 9 8 9 7 9 9 9 9 9 9 8 7 7 7 9 13 8 5 9 9 9 8 7 9 8 7 8 8 7 8 7 9 8 9 7 7 8 9 9 9 9 9 9 9 9 6 9 8 9 6 9 8