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