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