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