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