1500 123 861
483 551 119 412 275 97 120 0 168 806 400 728 388 474 902 148 242 640 942 158 954 823 356 916 309 248 147 507 177 220 863 795 188 587 387 661 198 766 917 164 832 592 432 932 979 836 522 182 843 956 915 540 821 85 26 600 661 663 128 797 472 897 195 171 927 649 493 600 596 216 728 526 174 255 437 930 71 250 553 496 214 163 767 863 83 143 115 63 507 263 610 2 623 1 356 510 672 460 713 578 854 295 819 847 329 551 581 163 967 531 52 852 570 956 210 469 645 94 54 83 664 180 683 338 766 997 73 646 79 690 979 626 388 856 54 852 281 47 728 524 265 371 105 977 972 998 327 746 82 168 625 593 387 327 244 672 126 636 146 995 483 315 314 10 382 884 320 169 463 760 249 41 334 617 46 881 340 662 377 743 303 422 481 509 155 12 545 910 496 628 323 581 440 110 96 582 99 849 387 681 126 591 600 248 730 90 768 460 72 307 187 704 913 942 394 357 500 256 654 838 661 576 34 612 742 286 890 18 861 498 915 643 751 628 465 829 188 651 136 504 6 887 97 446 709 774 787 99 790 393 628 431 389 324 137 787 752 937 352 886 213 705 476 337 66 72 199 758 933 183 445 421 639 471 112 909 163 507 643 171 847 414 816 793 537 189 876 819 764 783 488 925 396 807 766 665 662 884 947 813 395 216 684 84 359 380 350 672 912 86 31 59 186 348 962 57 244 660 988 251 859 117 613 834 396 48 433 613 463 54 545 617 929 295 569 266 638 849 697 821 821 472 993 759 157 168 899 525 268 443 664 53 952 725 737 15 371 757 90 189 148 503 466 665 574 964 992 392 196 209 526 320 213 281 7 586 865 283 270 340 137 246 517 466 101 44 859 654 824 412 125 12 279 326 700 785 80 267 122 783 603 581 272 759 644 683 140 971 876 803 584 255 363 169 955 887 33 971 435 724 953 565 361 117 522 414 378 799 20 741 636 599 390 454 587 851 535 325 200 453 143 331 352 601 661 238 96 650 294 318 364 919 721 655 79 606 828 51 153 223 951 720 285 615 732 193 462 860 117 472 795 217 52 370 485 346 856 165 438 191 781 413 483 109 96 426 181 59 128 323 841 972 693 960 601 928 166 631 588 662 133 236 213 253 345 683 412 127 734 272 660 421 229 99 571 736 848 934 993 171 985 324 332 492 193 359 548 659 226 450 695 375 380 354 185 913 990 239 24 847 362 73 767 18 180 897 611 540 201 410 994 849 299 106 643 294 354 721 27 120 273 963 182 948 502 870 251 491 271 605 453 108 74 478 210 38 80 549 29 585 691 868 321 934 451 894 218 922 720 582 617 179 646 836 417 709 734 645 264 119 382 658 218 283 198 606 592 924 980 247 112 47 562 33 542 587 258 456 951 241 785 546 527 297 799 679 797 296 872 267 871 456 85 162 96 719 622 718 22 523 501 744 655 946 347 225 133 618 249 421 176 767 390 252 528 15 698 840 480 618 132 740 200 613 101 157 627 625 171 401 951 643 551 501 391 328 955 249 49 272 206 812 199 806 861 232 557 419 680 940 728 414 758 641 783 4 933 189 202 92 849 39 429 466 338 317 683 852 426 288 202 526 740 836 844 36 23 121 120 777 497 592 777 697 711 818 157 711 13 406 464 162 927 203 268 911 806 516 866 559 648 326 330 764 982 158 731 559 620 373 55 684 539 33 648 483 908 452 393 662 565 231 357 41 204 685 374 374 122 796 882 544 882 835 346 166 468 836 970 801 242 883 894 275 25 382 905 515 308 782 640 397 243 376 109 375 292 547 301 599 246 930 953 963 556 518 343 179 54 923 479 935 589 668 867 563 425 423 89 400 772 510 126 796 484 846 544 302 156 318 135 740 337 137 970 983 175 609 32 356 39 631 225 429 535 99 51 268 843 915 81 423 139 671 569 102 910 265 618 943 189 376 822 451 447 947 705 91 0 149 790 30 559 166 920 815 976 112 483 434 49 129 958 876 997 746 868 942 83 480 897 848 362 715 267 907 988 670 270 65 193 57 424 581 234 782 550 832 337 186 28 122 149 58 359 757 791 3 483 691 5 420 618 939 592 872 576 337 640 581 234 650 832 2 809 710 478 633 67 103 113 513 779 478 436 752 260 119 626 380 364 733 829 50 715 4 798 694 91 458 427 135 845 742 392 875 717 314 544 620 929 83 662 886 674 685 456 483 346 406 935 707 938 29 61 699 340 800 294 569 631 326 604 382 192 345 511 169 563 708 674 201 712 569 312 669 562 344 89 324 309 864 756 80 354 669 155 444 918 297 79 337 661 910 135 309 187 656 649 752 8 726 164 256 410 265 65 981 554 98 48 409 340 393 21 881 598 208 386 376 266 462 785 28 725 361 528 849 50 325 761 969 769 847 311 695 54 86 491 100 459 844 803 476 359 840 448 641 115 729 588 512 892 466 358 353 472 453 42 628 190 30 17 155 223 160 14 996 550 768 551 403 208 373 178 353 263 947 674 194 462 412 838 325 710 547 832 927 126 288 595 760 639 327 745 445 328 671 613 393 523 941 65 140 651 92 690 729 201 427 919 956 838 168 20 120 532 74 641 571 314 739 482 964 906 231 663 392 17 607 857 300 796 813 542 282 59 234 374 489 520 729 822 434 262 38 707 382 958 56 715 590 376 906 656 297 599 592 992 981 441 166 507 898 558 136 776 160 494 207 763 318 70 957 93 436 509 470 507 109 30 189 959 186 594 307 775 820 852 550 297 123 856 467 757 426 355 179 697 346 833 830 366 884 945 478 476 371 294 23 430 536 569 490 29 433 282 610 106 816 933 458 229 802 117 419 575 786 432 826 965 124 6 182 426 558 667 819 93 569 681 129 326 993 951 966 797 861 847 51 336 135 722 854 458 849 564 174 10 109 19 8 255 994 780 490 101 479 887 835 558 14 2 911 208 432 340 991 556 456 482 49 673 368 785 806 702 179 512 771 399 645 27 166 28 699 652 781 609 161 20 395 883 82 864 860 319 534 366 766 5 435 817 502 784 422 160 101 106 477 509 983 440 811 589 58 388 774 908 432 209 690 921 518 728 174 842 711 667 943 734 598 999 729 761 502 983 992 150 49 317 266 790 388 572 182 353 429 406 62 601 795 301 789 949 335 781 615 889 939 99 704 392 78 118 560 913 816 788 684 161 869 724 315 860 7 244 704 995 497 46 627 710 450 159 166 282 869 904 910 144 61 795 90 72 865 393 566 429 94 154 428 667 364 154 337 542 615 54 892 444 368 551 748 701 604 146 210 376 93 141 988 77 752 609 677 780 283 730 851 73 378 79 572 555 920 984 998 28 692 33 505 760 665 198 708 900 23 521 391 72 875 579 310 518 955 945 255 943 443