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