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