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