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