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