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