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