Input
465 473 998 257 0 385 664 707 147 929 87 450 748 938 998 768 234 722 851 113 700 957 265 284 250 137 317 801 128 820 321 612 956 434 534 621 651 129 421 337 216 699 347 101 464 601 87 563 738 635 386 972 620 851 948 200 156 571 551 522 828 984 514 378 363 484 855 869 835 234 1085 764 230 885
Output
87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 87 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 234 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 113 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 129 147 147 147 147 147 147 147 147 147 147 147 147 147 147 147 147 147 147 147 147 147 147 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 250 137 137 137 137 137 137 137 137 137 137 137 137 137 137 137 137 137 137 137 137 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 121 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 128 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 230 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 50 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 101 156 156 156 156 156 156 156 156 156 156 156 156 156 156 156 156 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 216 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 257 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 284 337 337 337 337 337 337 337 337 337 337 337 337 337 337 337 337 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 378 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 386 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 635 16 16 16 16 16 16 16 16 16 16 16 16 16 16 265 265 265 265 265 265 265 265 265 265 265 265 265 265 317 317 317 317 317 317 317 317 317 317 317 317 317 317 347 347 347 347 347 347 347 347 347 347 347 347 347 347 363 363 363 363 363 363 363 363 363 363 363 363 363 363 401 401 401 401 401 401 401 401 401 401 401 401 401 401 464 464 464 464 464 464 464 464 464 464 464 464 464 464 484 484 484 484 484 484 484 484 484 484 484 484 484 484 514 514 514 514 514 514 514 514 514 514 514 514 514 514 534 534 534 534 534 534 534 534 534 534 534 534 534 534 117 117 117 117 117 117 117 117 117 117 117 117 117 34 34 34 34 34 34 34 34 34 34 34 34 49 49 49 49 49 49 49 49 49 49 49 49 136 136 136 136 136 136 136 136 136 136 136 136 249 249 249 249 249 249 249 249 249 249 249 249 321 321 321 321 321 321 321 321 321 321 321 321 336 336 336 336 336 336 336 336 336 336 336 336 385 385 385 385 385 385 385 385 385 385 385 385 421 421 421 421 421 421 421 421 421 421 421 421 435 435 435 435 435 435 435 435 435 435 435 435 465 465 465 465 465 465 465 465 465 465 465 465 473 473 473 473 473 473 473 473 473 473 473 473 601 601 601 601 601 601 601 601 601 601 601 601 651 651 651 651 651 651 651 651 651 651 651 651 41 41 41 41 41 41 41 41 41 41 41 185 185 185 185 185 185 185 185 185 185 185 8 8 8 8 8 8 8 8 8 8 69 69 69 69 69 69 69 69 69 69 79 79 79 79 79 79 79 79 79 79 103 103 103 103 103 103 103 103 103 103 106 106 106 106 106 106 106 106 106 106 144 144 144 144 144 144 144 144 144 144 170 170 170 170 170 170 170 170 170 170 178 178 178 178 178 178 178 178 178 178 208 208 208 208 208 208 208 208 208 208 298 298 298 298 298 298 298 298 298 298 314 314 314 314 314 314 314 314 314 314 434 434 434 434 434 434 434 434 434 434 450 450 450 450 450 450 450 450 450 450 488 488 488 488 488 488 488 488 488 488 522 522 522 522 522 522 522 522 522 522 612 612 612 612 612 612 612 612 612 612 620 620 620 620 620 620 620 620 620 620 621 621 621 621 621 621 621 621 621 621 722 722 722 722 722 722 722 722 722 722 764 764 764 764 764 764 764 764 764 764 571 571 571 571 571 571 571 571 571 14 14 14 14 14 14 14 14 15 15 15 15 15 15 15 15 19 19 19 19 19 19 19 19 20 20 20 20 20 20 20 20 23 23 23 23 23 23 23 23 26 26 26 26 26 26 26 26 27 27 27 27 27 27 27 27 30 30 30 30 30 30 30 30 31 31 31 31 31 31 31 31 60 60 60 60 60 60 60 60 64 64 64 64 64 64 64 64 72 72 72 72 72 72 72 72 78 78 78 78 78 78 78 78 97 97 97 97 97 97 97 97 98 98 98 98 98 98 98 98 133 133 133 133 133 133 133 133 148 148 148 148 148 148 148 148 151 151 151 151 151 151 151 151 152 152 152 152 152 152 152 152 163 163 163 163 163 163 163 163 171 171 171 171 171 171 171 171 187 187 187 187 187 187 187 187 193 193 193 193 193 193 193 193 197 197 197 197 197 197 197 197 235 235 235 235 235 235 235 235 273 273 273 273 273 273 273 273 288 288 288 288 288 288 288 288 306 306 306 306 306 306 306 306 334 334 334 334 334 334 334 334 351 351 351 351 351 351 351 351 355 355 355 355 355 355 355 355 371 371 371 371 371 371 371 371 405 405 405 405 405 405 405 405 483 483 483 483 483 483 483 483 507 507 507 507 507 507 507 507 548 548 548 548 548 548 548 548 551 551 551 551 551 551 551 551 563 563 563 563 563 563 563 563 594 594 594 594 594 594 594 594 714 714 714 714 714 714 714 714 738 738 738 738 738 738 738 738 748 748 748 748 748 748 748 748 768 768 768 768 768 768 768 768 367 367 367 367 367 367 367 367 851 851 851 851 851 851 851 851 57 57 57 57 57 57 57 1 1 1 1 1 1 4 4 4 4 4 4 9 9 9 9 9 9 18 18 18 18 18 18 42 42 42 42 42 42 43 43 43 43 43 43 63 63 63 63 63 63 65 65 65 65 65 65 71 71 71 71 71 71 80 80 80 80 80 80 83 83 83 83 83 83 84 84 84 84 84 84 88 88 88 88 88 88 99 99 99 99 99 99 102 102 102 102 102 102 105 105 105 105 105 105 143 143 143 143 143 143 167 167 167 167 167 167 177 177 177 177 177 177 180 180 180 180 180 180 186 186 186 186 186 186 191 191 191 191 191 191 204 204 204 204 204 204 214 214 214 214 214 214 226 226 226 226 226 226 231 231 231 231 231 231 238 238 238 238 238 238 239 239 239 239 239 239 254 254 254 254 254 254 264 264 264 264 264 264 272 272 272 272 272 272 280 280 280 280 280 280 291 291 291 291 291 291 299 299 299 299 299 299 300 300 300 300 300 300 304 304 304 304 304 304 318 318 318 318 318 318 322 322 322 322 322 322 328 328 328 328 328 328 344 344 344 344 344 344 370 370 370 370 370 370 377 377 377 377 377 377 387 387 387 387 387 387 397 397 397 397 397 397 417 417 417 417 417 417 427 427 427 427 427 427 442 442 442 442 442 442 447 447 447 447 447 447 491 491 491 491 491 491 492 492 492 492 492 492 499 499 499 499 499 499 504 504 504 504 504 504 508 508 508 508 508 508 538 538 538 538 538 538 564 564 564 564 564 564 570 570 570 570 570 570 586 586 586 586 586 586 617 617 617 617 617 617 664 664 664 664 664 664 681 681 681 681 681 681 699 699 699 699 699 699 700 700 700 700 700 700 707 707 707 707 707 707 741 741 741 741 741 741 782 782 782 782 782 782 801 801 801 801 801 801 828 828 828 828 828 828 869 869 869 869 869 869 885 885 885 885 885 885 155 155 155 155 155 243 243 243 243 243 313 313 313 313 313 329 329 329 329 329 443 443 443 443 443 585 585 585 585 585 7 7 7 7 10 10 10 10 12 12 12 12 28 28 28 28 29 29 29 29 35 35 35 35 36 36 36 36 37 37 37 37 38 38 38 38 39 39 39 39 44 44 44 44 46 46 46 46 48 48 48 48 52 52 52 52 53 53 53 53 56 56 56 56 58 58 58 58 67 67 67 67 68 68 68 68 74 74 74 74 86 86 86 86 90 90 90 90 93 93 93 93 94 94 94 94 100 100 100 100 107 107 107 107 110 110 110 110 118 118 118 118 120 120 120 120 149 149 149 149 150 150 150 150 162 162 162 162 164 164 164 164 165 165 165 165 166 166 166 166 169 169 169 169 181 181 181 181 184 184 184 184 188 188 188 188 189 189 189 189 199 199 199 199 201 201 201 201 205 205 205 205 207 207 207 207 215 215 215 215 218 218 218 218 219 219 219 219 220 220 220 220 223 223 223 223 224 224 224 224 227 227 227 227 236 236 236 236 242 242 242 242 246 246 246 246 248 248 248 248 258 258 258 258 260 260 260 260 274 274 274 274 276 276 276 276 277 277 277 277 278 278 278 278 279 279 279 279 286 286 286 286 287 287 287 287 292 292 292 292 294 294 294 294 301 301 301 301 303 303 303 303 308 308 308 308 327 327 327 327 333 333 333 333 335 335 335 335 352 352 352 352 356 356 356 356 360 360 360 360 362 362 362 362 364 364 364 364 61 61 61 61 375 375 375 375 382 382 382 382 383 383 383 383 390 390 390 390 394 394 394 394 404 404 404 404 407 407 407 407 414 414 414 414 415 415 415 415 416 416 416 416 423 423 423 423 430 430 430 430 438 438 438 438 454 454 454 454 457 457 457 457 466 466 466 466 470 470 470 470 472 472 472 472 476 476 476 476 498 498 498 498 500 500 500 500 506 506 506 506 511 511 511 511 518 518 518 518 525 525 525 525 530 530 530 530 533 533 533 533 536 536 536 536 544 544 544 544 552 552 552 552 567 567 567 567 577 577 577 577 578 578 578 578 598 598 598 598 609 609 609 609 613 613 613 613 619 619 619 619 639 639 639 639 655 655 655 655 661 661 661 661 672 672 672 672 673 673 673 673 677 677 677 677 688 688 688 688 691 691 691 691 695 695 695 695 704 704 704 704 723 723 723 723 727 727 727 727 733 733 733 733 750 750 750 750 756 756 756 756 798 798 798 798 820 820 820 820 835 835 835 835 842 842 842 842 855 855 855 855 861 861 861 861 870 870 870 870 897 897 897 897 911 911 911 911 998 998 998 998 217 217 217 391 391 391 451 451 451 517 517 517 625 625 625 11 11 13 13 22 22 24 24 33 33 54 54 55 55 70 70 82 82 91 91 95 95 104 104 109 109 115 115 122 122 126 126 127 127 130 130 131 131 135 135 142 142 159 159 161 161 173 173 174 174 175 175 183 183 190 190 192 192 209 209 210 210 213 213 221 221 222 222 229 229 241 241 256 256 262 262 266 266 267 267 268 268 269 269 275 275 283 283 285 285 293 293 295 295 297 297 305 305 309 309 320 320 326 326 330 330 341 341 343 343 345 345 349 349 353 353 358 358 366 366 372 372 379 379 380 380 393 393 395 395 396 396 399 399 406 406 409 409 412 412 413 413 419 419 420 420 422 422 424 424 426 426 431 431 433 433 445 445 448 448 449 449 456 456 458 458 462 462 469 469 474 474 475 475 477 477 479 479 480 480 481 481 493 493 495 495 503 503 519 519 520 520 523 523 527 527 532 532 535 535 543 543 550 550 553 553 560 560 562 562 566 566 568 568 572 572 575 575 579 579 582 582 587 587 590 590 591 591 592 592 593 593 599 599 604 604 605 605 606 606 608 608 610 610 611 611 627 627 628 628 631 631 636 636 637 637 640 640 645 645 647 647 654 654 663 663 667 667 669 669 679 679 683 683 692 692 698 698 706 706 708 708 713 713 715 715 718 718 719 719 726 726 729 729 732 732 734 734 740 740 742 742 754 754 757 757 772 772 784 784 792 792 800 800 809 809 810 810 816 816 819 819 825 825 837 837 843 843 844 844 847 847 856 856 871 871 929 929 938 938 948 948 956 956 957 957 972 972 984 984 17 1085 139 157 315 359 411 555 653 685 773 791 811 827 829 859 883