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