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