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