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