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