0 0 1 1 2 2 3 2 4 3 5 3 6 4 7 5 8 5 9 6 10 6 11 7 12 8 13 8 14 9 15 9 16 10 17 10 18 11 19 12 20 12 21 13 22 13 23 14 24 15 25 15 26 16 27 16 28 17 29 17 30 18 31 19 32 19 33 20 34 20 35 21 36 22 37 22 38 23 39 23 40 24 41 24 42 25 43 26 44 26 45 27 46 27 47 28 48 29 49 29 50 30 51 30 52 31 53 32 54 32 55 33 56 33 57 34 58 34 59 35 60 36 61 36 62 37 63 37 64 38 65 39 66 39 67 40 68 40 69 41 70 41 71 42 72 43 73 43 74 44 75 44 76 45 77 46 78 46 79 47 80 47 81 48 82 48 83 49 84 50 85 50 86 51 87 51 88 52 89 53 90 53 91 54 92 54 93 55 94 55 95 56 96 57 97 57 98 58 99 58 100 59 101 60 102 60 103 61 104 61 105 62 106 63 107 63 108 64 109 64 110 65 111 65 112 66 113 67 114 67 115 68 116 68 117 69 118 70 119 70 120 71 121 71 122 72 123 72 124 73 125 74 126 74 127 75 128 75 129 76 130 77 131 77 132 78 133 78 134 79 135 79 136 80 137 81 138 81 139 82 140 82 141 83 142 84 143 84 144 85 145 85 146 86 147 86 148 87 149 88 150 88 151 89 152 89 153 90 154 91 155 91 156 92 157 92 158 93 159 94 160 94 161 95 162 95 163 96 164 96 165 97 166 98 167 98 168 99 169 99 170 100 171 101 172 101 173 102 174 102 175 103 176 103 177 104 178 105 179 105 180 106 181 106 182 107 183 108 184 108 185 109 186 109 187 110 188 110 189 111 190 112 191 112 192 113 193 113 194 114 195 115 196 115 197 116 198 116 199 117 200 117 201 118 202 119 203 119 204 120 205 120 206 121 207 122 208 122 209 123 210 123 211 124 212 125 213 125 214 126 215 126 216 127 217 127 218 128 219 129 220 129 221 130 222 130 223 131 224 132 225 132 226 133 227 133 228 134 229 134 230 135 231 136 232 136 233 137 234 137 235 138 236 139 237 139 238 140 239 140 240 141 241 141 242 142 243 143 244 143 245 144 246 144 247 145 248 146 249 146 250 147 251 147 252 148 253 148 254 149 255 150 256 150 257 151 258 151 259 152 260 153 261 153 262 154 263 154 264 155 265 156 266 156 267 157 268 157 269 158 270 158 271 159 272 160 273 160 274 161 275 161 276 162 277 163 278 163 279 164 280 164 281 165 282 165 283 166 284 167 285 167 286 168 287 168 288 169 289 170 290 170 291 171 292 171 293 172 294 172 295 173 296 174 297 174 298 175 299 175 300 176 301 177 302 177 303 178 304 178 305 179 306 179 307 180 308 181 309 181 310 182 311 182 312 183 313 184 314 184 315 185 316 185 317 186 318 187 319 187 320 188 321 188 322 189 323 189 324 190 325 191 326 191 327 192 328 192 329 193 330 194 331 194 332 195 333 195 334 196 335 196 336 197 337 198 338 198 339 199 340 199 341 200 342 201 343 201 344 202 345 202 346 203 347 203 348 204 349 205 350 205 351 206 352 206 353 207 354 208 355 208 356 209 357 209 358 210 359 211 360 211 361 212 362 212 363 213 364 213 365 214 366 215 367 215 368 216 369 216 370 217 371 218 372 218 373 219 374 219 375 220 376 220 377 221 378 222 379 222 380 223 381 223 382 224 383 225 384 225 385 226 386 226 387 227 388 227 389 228 390 229 391 229 392 230 393 230 394 231 395 232 396 232 397 233 398 233 399 234 400 234 401 235 402 236 403 236 404 237 405 237 406 238 407 239 408 239 409 240 410 240 411 241 412 242 413 242 414 243 415 243 416 244 417 244 418 245 419 246 420 246 421 247 422 247 423 248 424 249 425 249 426 250 427 250 428 251 429 251 430 252 431 253 432 253 433 254 434 254 435 255 436 256 437 256 438 257 439 257 440 258 441 258 442 259 443 260 444 260 445 261 446 261 447 262 448 263 449 263 450 264 451 264 452 265 453 265 454 266 455 267 456 267 457 268 458 268 459 269 460 270 461 270 462 271 463 271 464 272 465 273 466 273 467 274 468 274 469 275 470 275 471 276 472 277 473 277 474 278 475 278 476 279 477 280 478 280 479 281 480 281 481 282 482 282 483 283 484 284 485 284 486 285 487 285 488 286 489 287 490 287 491 288 492 288 493 289 494 289 495 290 496 291 497 291 498 292 499 292 500 293 501 294 502 294 503 295 504 295 505 296 506 296 507 297 508 298 509 298 510 299 511 299 512 300 513 301 514 301 515 302 516 302 517 303 518 304 519 304 520 305 521 305 522 306 523 306 524 307 525 308 526 308 527 309 528 309 529 310 530 311 531 311 532 312 533 312 534 313 535 313 536 314 537 315 538 315 539 316 540 316 541 317 542 318 543 318 544 319 545 319 546 320 547 320 548 321 549 322 550 322 551 323 552 323 553 324 554 325 555 325 556 326 557 326 558 327 559 327 560 328 561 329 562 329 563 330 564 330 565 331 566 332 567 332 568 333 569 333 570 334 571 335 572 335 573 336 574 336 575 337 576 337 577 338 578 339 579 339 580 340 581 340 582 341 583 342 584 342 585 343 586 343 587 344 588 344 589 345 590 346 591 346 592 347 593 347 594 348 595 349 596 349 597 350 598 350 599 351 600 351 601 352 602 353 603 353 604 354 605 354 606 355 607 356 608 356 609 357 610 357 611 358 612 358 613 359 614 360 615 360 616 361 617 361 618 362 619 363 620 363 621 364 622 364 623 365 624 366 625 366 626 367 627 367 628 368 629 368 630 369 631 370 632 370 633 371 634 371 635 372 636 373 637 373 638 374 639 374 640 375 641 375 642 376 643 377 644 377 645 378 646 378 647 379 648 380 649 380 650 381 651 381 652 382 653 382 654 383 655 384 656 384 657 385 658 385 659 386 660 387 661 387 662 388 663 388 664 389 665 390 666 390 667 391 668 391 669 392 670 392 671 393 672 394 673 394 674 395 675 395 676 396 677 397 678 397 679 398 680 398 681 399 682 399 683 400 684 401 685 401 686 402 687 402 688 403 689 404 690 404 691 405 692 405 693 406 694 406 695 407 696 408 697 408 698 409 699 409 700 410 701 411 702 411 703 412 704 412 705 413 706 413 707 414 708 415 709 415 710 416 711 416 712 417 713 418 714 418 715 419 716 419 717 420 718 421 719 421 720 422 721 422 722 423 723 423 724 424 725 425 726 425 727 426 728 426 729 427 730 428 731 428 732 429 733 429 734 430 735 430 736 431 737 432 738 432 739 433 740 433 741 434 742 435 743 435 744 436 745 436 746 437 747 437 748 438 749 439 750 439 751 440 752 440 753 441 754 442 755 442 756 443 757 443 758 444 759 444 760 445 761 446 762 446 763 447 764 447 765 448 766 449 767 449 768 450 769 450 770 451 771 452 772 452 773 453 774 453 775 454 776 454 777 455 778 456 779 456 780 457 781 457 782 458 783 459 784 459 785 460 786 460 787 461 788 461 789 462 790 463 791 463 792 464 793 464 794 465 795 466 796 466 797 467 798 467 799 468 800 468 801 469 802 470 803 470 804 471 805 471 806 472 807 473 808 473 809 474 810 474 811 475 812 475 813 476 814 477 815 477 816 478 817 478 818 479 819 480 820 480 821 481 822 481 823 482 824 483 825 483 826 484 827 484 828 485 829 485 830 486 831 487 832 487 833 488 834 488 835 489 836 490 837 490 838 491 839 491 840 492 841 492 842 493 843 494 844 494 845 495 846 495 847 496 848 497 849 497 850 498 851 498 852 499 853 499 854 500 855 501 856 501 857 502 858 502 859 503 860 504 861 504 862 505 863 505 864 506 865 506 866 507 867 508 868 508 869 509 870 509 871 510 872 511 873 511 874 512 875 512 876 513 877 514 878 514 879 515 880 515 881 516 882 516 883 517 884 518 885 518 886 519 887 519 888 520 889 521 890 521 891 522 892 522 893 523 894 523 895 524 896 525 897 525 898 526 899 526 900 527 901 528 902 528 903 529 904 529 905 530 906 530 907 531 908 532 909 532 910 533 911 533 912 534 913 535 914 535 915 536 916 536 917 537 918 537 919 538 920 539 921 539 922 540 923 540 924 541 925 542 926 542 927 543 928 543 929 544 930 545 931 545 932 546 933 546 934 547 935 547 936 548 937 549 938 549 939 550 940 550 941 551 942 552 943 552 944 553 945 553 946 554 947 554 948 555 949 556 950 556 951 557 952 557 953 558 954 559 955 559 956 560 957 560 958 561 959 561 960 562 961 563 962 563 963 564 964 564 965 565 966 566 967 566 968 567 969 567 970 568 971 568 972 569 973 570 974 570 975 571 976 571 977 572 978 573 979 573 980 574 981 574 982 575 983 576 984 576 985 577 986 577 987 578 988 578 989 579 990 580 991 580 992 581 993 581 994 582 995 583 996 583 997 584 998 584 999 585 1000 585