0 1 1 1 2 1 3 1 4 0 5 1 6 1 7 0 8 0 9 1 10 1 11 0 12 1 13 0 14 1 15 1 16 0 17 1 18 1 19 0 20 1 21 1 22 0 23 1 24 0 25 1 26 0 27 1 28 1 29 0 30 1 31 0 32 0 33 1 34 0 35 1 36 1 37 0 38 1 39 0 40 1 41 0 42 1 43 0 44 1 45 1 46 0 47 1 48 0 49 1 50 1 51 0 52 1 53 0 54 1 55 1 56 0 57 1 58 0 59 1 60 0 61 1 62 0 63 1 64 0 65 1 66 1 67 0 68 1 69 0 70 1 71 0 72 0 73 1 74 0 75 1 76 0 77 1 78 1 79 0 80 1 81 0 82 1 83 0 84 1 85 0 86 1 87 0 88 1 89 0 90 1 91 1 92 0 93 1 94 0 95 1 96 0 97 1 98 1 99 0 100 1 101 0 102 1 103 0 104 1 105 1 106 0 107 1 108 0 109 1 110 0 111 1 112 0 113 1 114 0 115 1 116 0 117 1 118 0 119 1 120 1 121 0 122 1 123 0 124 1 125 0 126 1 127 0 128 0 129 1 130 0 131 1 132 0 133 1 134 0 135 1 136 1 137 0 138 1 139 0 140 1 141 0 142 1 143 0 144 1 145 0 146 1 147 0 148 1 149 0 150 1 151 0 152 1 153 1 154 0 155 1 156 0 157 1 158 0 159 1 160 0 161 1 162 1 163 0 164 1 165 0 166 1 167 0 168 1 169 0 170 1 171 1 172 0 173 1 174 0 175 1 176 0 177 1 178 0 179 1 180 0 181 1 182 0 183 1 184 0 185 1 186 0 187 1 188 0 189 1 190 1 191 0 192 1 193 0 194 1 195 0 196 1 197 0 198 1 199 0 200 0 201 1 202 0 203 1 204 0 205 1 206 0 207 1 208 0 209 1 210 1 211 0 212 1 213 0 214 1 215 0 216 1 217 0 218 1 219 0 220 1 221 0 222 1 223 0 224 1 225 0 226 1 227 0 228 1 229 0 230 1 231 1 232 0 233 1 234 0 235 1 236 0 237 1 238 0 239 1 240 0 241 1 242 1 243 0 244 1 245 0 246 1 247 0 248 1 249 0 250 1 251 0 252 1 253 1 254 0 255 1 256 0 257 1 258 0 259 1 260 0 261 1 262 0 263 1 264 0 265 1 266 0 267 1 268 0 269 1 270 0 271 1 272 0 273 1 274 0 275 1 276 1 277 0 278 1 279 0 280 1 281 0 282 1 283 0 284 1 285 0 286 1 287 0 288 0 289 1 290 0 291 1 292 0 293 1 294 0 295 1 296 0 297 1 298 0 299 1 300 1 301 0 302 1 303 0 304 1 305 0 306 1 307 0 308 1 309 0 310 1 311 0 312 1 313 0 314 1 315 0 316 1 317 0 318 1 319 0 320 1 321 0 322 1 323 0 324 1 325 1 326 0 327 1 328 0 329 1 330 0 331 1 332 0 333 1 334 0 335 1 336 0 337 1 338 1 339 0 340 1 341 0 342 1 343 0 344 1 345 0 346 1 347 0 348 1 349 0 350 1 351 1 352 0 353 1 354 0 355 1 356 0 357 1 358 0 359 1 360 0 361 1 362 0 363 1 364 0 365 1 366 0 367 1 368 0 369 1 370 0 371 1 372 0 373 1 374 0 375 1 376 0 377 1 378 1 379 0 380 1 381 0 382 1 383 0 384 1 385 0 386 1 387 0 388 1 389 0 390 1 391 0 392 0 393 1 394 0 395 1 396 0 397 1 398 0 399 1 400 0 401 1 402 0 403 1 404 0 405 1 406 1 407 0 408 1 409 0 410 1 411 0 412 1 413 0 414 1 415 0 416 1 417 0 418 1 419 0 420 1 421 0 422 1 423 0 424 1 425 0 426 1 427 0 428 1 429 0 430 1 431 0 432 1 433 0 434 1 435 1 436 0 437 1 438 0 439 1 440 0 441 1 442 0 443 1 444 0 445 1 446 0 447 1 448 0 449 1 450 1 451 0 452 1 453 0 454 1 455 0 456 1 457 0 458 1 459 0 460 1 461 0 462 1 463 0 464 1 465 1 466 0 467 1 468 0 469 1 470 0 471 1 472 0 473 1 474 0 475 1 476 0 477 1 478 0 479 1 480 0 481 1 482 0 483 1 484 0 485 1 486 0 487 1 488 0 489 1 490 0 491 1 492 0 493 1 494 0 495 1 496 1 497 0 498 1 499 0 500 1 501 0 502 1 503 0 504 1 505 0 506 1 507 0 508 1 509 0 510 1 511 0 512 0 513 1 514 0 515 1 516 0 517 1 518 0 519 1 520 0 521 1 522 0 523 1 524 0 525 1 526 0 527 1 528 1 529 0 530 1 531 0 532 1 533 0 534 1 535 0 536 1 537 0 538 1 539 0 540 1 541 0 542 1 543 0 544 1 545 0 546 1 547 0 548 1 549 0 550 1 551 0 552 1 553 0 554 1 555 0 556 1 557 0 558 1 559 0 560 1 561 1 562 0 563 1 564 0 565 1 566 0 567 1 568 0 569 1 570 0 571 1 572 0 573 1 574 0 575 1 576 0 577 1 578 1 579 0 580 1 581 0 582 1 583 0 584 1 585 0 586 1 587 0 588 1 589 0 590 1 591 0 592 1 593 0 594 1 595 1 596 0 597 1 598 0 599 1 600 0 601 1 602 0 603 1 604 0 605 1 606 0 607 1 608 0 609 1 610 0 611 1 612 0 613 1 614 0 615 1 616 0 617 1 618 0 619 1 620 0 621 1 622 0 623 1 624 0 625 1 626 0 627 1 628 0 629 1 630 1 631 0 632 1 633 0 634 1 635 0 636 1 637 0 638 1 639 0 640 1 641 0 642 1 643 0 644 1 645 0 646 1 647 0 648 0 649 1 650 0 651 1 652 0 653 1 654 0 655 1 656 0 657 1 658 0 659 1 660 0 661 1 662 0 663 1 664 0 665 1 666 1 667 0 668 1 669 0 670 1 671 0 672 1 673 0 674 1 675 0 676 1 677 0 678 1 679 0 680 1 681 0 682 1 683 0 684 1 685 0 686 1 687 0 688 1 689 0 690 1 691 0 692 1 693 0 694 1 695 0 696 1 697 0 698 1 699 0 700 1 701 0 702 1 703 1 704 0 705 1 706 0 707 1 708 0 709 1 710 0 711 1 712 0 713 1 714 0 715 1 716 0 717 1 718 0 719 1 720 0 721 1 722 1 723 0 724 1 725 0 726 1 727 0 728 1 729 0 730 1 731 0 732 1 733 0 734 1 735 0 736 1 737 0 738 1 739 0 740 1 741 1 742 0 743 1 744 0 745 1 746 0 747 1 748 0 749 1 750 0 751 1 752 0 753 1 754 0 755 1 756 0 757 1 758 0 759 1 760 0 761 1 762 0 763 1 764 0 765 1 766 0 767 1 768 0 769 1 770 0 771 1 772 0 773 1 774 0 775 1 776 0 777 1 778 0 779 1 780 1 781 0 782 1 783 0 784 1 785 0 786 1 787 0 788 1 789 0 790 1 791 0 792 1 793 0 794 1 795 0 796 1 797 0 798 1 799 0 800 0 801 1 802 0 803 1 804 0 805 1 806 0 807 1 808 0 809 1 810 0 811 1 812 0 813 1 814 0 815 1 816 0 817 1 818 0 819 1 820 1 821 0 822 1 823 0 824 1 825 0 826 1 827 0 828 1 829 0 830 1 831 0 832 1 833 0 834 1 835 0 836 1 837 0 838 1 839 0 840 1 841 0 842 1 843 0 844 1 845 0 846 1 847 0 848 1 849 0 850 1 851 0 852 1 853 0 854 1 855 0 856 1 857 0 858 1 859 0 860 1 861 1 862 0 863 1 864 0 865 1 866 0 867 1 868 0 869 1 870 0 871 1 872 0 873 1 874 0 875 1 876 0 877 1 878 0 879 1 880 0 881 1 882 1 883 0 884 1 885 0 886 1 887 0 888 1 889 0 890 1 891 0 892 1 893 0 894 1 895 0 896 1 897 0 898 1 899 0 900 1 901 0 902 1 903 1 904 0 905 1 906 0 907 1 908 0 909 1 910 0 911 1 912 0 913 1 914 0 915 1 916 0 917 1 918 0 919 1 920 0 921 1 922 0 923 1 924 0 925 1 926 0 927 1 928 0 929 1 930 0 931 1 932 0 933 1 934 0 935 1 936 0 937 1 938 0 939 1 940 0 941 1 942 0 943 1 944 0 945 1 946 1 947 0 948 1 949 0 950 1 951 0 952 1 953 0 954 1 955 0 956 1 957 0 958 1 959 0 960 1 961 0 962 1 963 0 964 1 965 0 966 1 967 0 968 0 969 1 970 0 971 1 972 0 973 1 974 0 975 1 976 0 977 1 978 0 979 1 980 0 981 1 982 0 983 1 984 0 985 1 986 0 987 1 988 0 989 1 990 1 991 0 992 1 993 0 994 1 995 0 996 1 997 0 998 1 999 0 1000 1 1001 0 1002 1 1003 0 1004 1 1005 0 1006 1 1007 0 1008 1 1009 0 1010 1 1011 0 1012 1 1013 0 1014 1 1015 0 1016 1 1017 0 1018 1 1019 0 1020 1 1021 0 1022 1 1023 0 1024 1 1025 0 1026 1 1027 0 1028 1 1029 0 1030 1 1031 0 1032 1 1033 0 1034 1 1035 1 1036 0 1037 1 1038 0 1039 1 1040 0 1041 1 1042 0 1043 1 1044 0 1045 1 1046 0 1047 1 1048 0 1049 1 1050 0 1051 1 1052 0 1053 1 1054 0 1055 1 1056 0 1057 1 1058 1 1059 0 1060 1 1061 0 1062 1 1063 0 1064 1 1065 0 1066 1 1067 0 1068 1 1069 0 1070 1 1071 0 1072 1 1073 0 1074 1 1075 0 1076 1 1077 0 1078 1 1079 0 1080 1 1081 1 1082 0 1083 1 1084 0 1085 1 1086 0 1087 1 1088 0 1089 1 1090 0 1091 1 1092 0 1093 1 1094 0 1095 1 1096 0 1097 1 1098 0 1099 1 1100 0 1101 1 1102 0 1103 1 1104 0 1105 1 1106 0 1107 1 1108 0 1109 1 1110 0 1111 1 1112 0 1113 1 1114 0 1115 1 1116 0 1117 1 1118 0 1119 1 1120 0 1121 1 1122 0 1123 1 1124 0 1125 1 1126 0 1127 1 1128 1 1129 0 1130 1 1131 0 1132 1 1133 0 1134 1 1135 0 1136 1 1137 0 1138 1 1139 0 1140 1 1141 0 1142 1 1143 0 1144 1 1145 0 1146 1 1147 0 1148 1 1149 0 1150 1 1151 0 1152 0 1153 1 1154 0 1155 1 1156 0 1157 1 1158 0 1159 1 1160 0 1161 1 1162 0 1163 1 1164 0 1165 1 1166 0 1167 1 1168 0 1169 1 1170 0 1171 1 1172 0 1173 1 1174 0 1175 1 1176 1 1177 0 1178 1 1179 0 1180 1 1181 0 1182 1 1183 0 1184 1 1185 0 1186 1 1187 0 1188 1 1189 0 1190 1 1191 0 1192 1 1193 0 1194 1 1195 0 1196 1 1197 0 1198 1 1199 0 1200 1 1201 0 1202 1 1203 0 1204 1 1205 0 1206 1 1207 0 1208 1 1209 0 1210 1 1211 0 1212 1 1213 0 1214 1 1215 0 1216 1 1217 0 1218 1 1219 0 1220 1 1221 0 1222 1 1223 0 1224 1 1225 1 1226 0 1227 1 1228 0 1229 1 1230 0 1231 1 1232 0 1233 1 1234 0 1235 1 1236 0 1237 1 1238 0 1239 1 1240 0 1241 1 1242 0 1243 1 1244 0 1245 1 1246 0 1247 1 1248 0 1249 1 1250 1 1251 0 1252 1 1253 0 1254 1 1255 0 1256 1 1257 0 1258 1 1259 0 1260 1 1261 0 1262 1 1263 0 1264 1 1265 0 1266 1 1267 0 1268 1 1269 0 1270 1 1271 0 1272 1 1273 0 1274 1 1275 1 1276 0 1277 1 1278 0 1279 1 1280 0 1281 1 1282 0 1283 1 1284 0 1285 1 1286 0 1287 1 1288 0 1289 1 1290 0 1291 1 1292 0 1293 1 1294 0 1295 1 1296 0 1297 1 1298 0 1299 1 1300 0 1301 1 1302 0 1303 1 1304 0 1305 1 1306 0 1307 1 1308 0 1309 1 1310 0 1311 1 1312 0 1313 1 1314 0 1315 1 1316 0 1317 1 1318 0 1319 1 1320 0 1321 1 1322 0 1323 1 1324 0 1325 1