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