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