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