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