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