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