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