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