0 1 1 1 2 1 3 1 4 1 5 2 6 1 7 1 8 2 9 3 10 1 11 2 12 2 13 3 14 5 15 1 16 3 17 2 18 3 19 5 20 7 21 2 22 5 23 3 24 4 25 6 26 7 27 11 28 3 29 8 30 5 31 6 32 6 33 8 34 11 35 15 36 7 37 13 38 9 39 9 40 9 41 10 42 12 43 16 44 22 45 11 46 20 47 15 48 17 49 14 50 15 51 16 52 18 53 24 54 30 55 18 56 30 57 26 58 28 59 22 60 27 61 21 62 25 63 27 64 33 65 42 66 36 67 45 68 43 69 46 70 38 71 44 72 33 73 43 74 36 75 44 76 47 77 60 78 46 79 66 80 64 81 70 82 63 83 72 84 61 85 69 86 60 87 63 88 58 89 69 90 80 91 88 92 99 93 96 94 106 95 105 96 115 97 100 98 112 99 102 100 104 101 91 102 110 103 94 104 117 105 125 106 140 107 137 108 166 109 155 110 185 111 164 112 185 113 166 114 173 115 158 116 172 117 136 118 175 119 161 120 183 121 205 122 215 123 229 124 244 125 264 126 255 127 288 128 273 129 287 130 266 131 286 132 239 133 268 134 234 135 266 136 270 137 303 138 302 139 348 140 347 141 398 142 394 143 438 144 427 145 453 146 433 147 467 148 408 149 444 150 408 151 403 152 370 153 471 154 418 155 474 156 488 157 518 158 563 159 603 160 639 161 653 162 703 163 697 164 741 165 682 166 740 167 674 168 672 169 622 170 658 171 653 172 714 173 668 174 734 175 757 176 855 177 855 178 958 179 971 180 1049 181 1064 182 1135 183 1095 184 1172 185 1115 186 1142 187 1060 188 1101 189 974 190 1144 191 1018 192 1108 193 1062 194 1164 195 1192 196 1294 197 1358 198 1440 199 1533 200 1616 201 1700 202 1709 203 1802 204 1797 205 1842 206 1768 207 1833 208 1661 209 1731 210 1744 211 1708 212 1644 213 1784 214 1677 215 1823 216 1892 217 2033 218 2087 219 2286 220 2284 221 2524 222 2556 223 2739 224 2761 225 2891 226 2832 227 2950 228 2797 229 2897 230 2653 231 2931 232 2676 233 2800 234 2583 235 2830 236 2707 237 2869 238 2936 239 3150 240 3251 241 3478 242 3634 243 3800 244 4030 245 4126 246 4320 247 4406 248 4601 249 4516 250 4665 251 4468 252 4498 253 4589 254 4525 255 4321 256 4454 257 4258 258 4413 259 4364 260 4560 261 4630 262 4920 263 5011 264 5322 265 5531 266 5881 267 6048 268 6456 269 6627 270 6973 271 6975 272 7300 273 7192 274 7344 275 7042 276 7607 277 7045 278 7330 279 6947 280 7100 281 6782 282 7197 283 6852 284 7270 285 7296 286 7677 287 7742 288 8351 289 8437 290 8962 291 9371 292 9803 293 10180 294 10606 295 10963 296 11174 297 11475 298 11362 299 11580 300 11801 301 11709 302 11490 303 11577 304 11292 305 11369 306 11044 307 11362 308 11140 309 11457 310 11562 311 11987 312 12079 313 12787 314 12995 315 13834 316 14189 317 15118 318 15416 319 16386 320 16716 321 17390 322 17602 323 18162 324 17844 325 19068 326 18326 327 18839 328 18214 329 18710 330 17926 331 18466 332 17665 333 18220 334 17787 335 18418 336 18168 337 18984 338 18989 339 19732 340 20099 341 21141 342 21765 343 22886 344 23732 345 24743 346 25777 347 26578 348 27305 349 27787 350 28357 351 29332 352 29388 353 29439 354 29885 355 29417 356 29568 357 29231 358 29242 359 28745 360 29189 361 28614 362 29097 363 29231 364 29524 365 29850 366 30946 367 31136 368 32574 369 33577 370 34861 371 36142 372 37980 373 38802 374 40679 375 41719 376 43071 377 43432 378 45934 379 45466 380 46938 381 46435 382 47694 383 46654 384 47756 385 46338 386 47321 387 46004 388 47133 389 45782 390 46955 391 46164 392 47375 393 46727 394 48493 395 48513 396 50476 397 51412 398 53884 399 54986 400 57725 401 59381 402 61684 403 63714 404 65589 405 67087 406 70158 407 70897 408 72330 409 73672 410 74253 411 74821 412 74969 413 75453 414 74971 415 75230 416 74385 417 74877 418 74308 419 74530 420 73828 421 75206 422 74719 423 75888 424 76603 425 78691 426 79784 427 82747 428 84495 429 87733 430 90536 431 94132 432 96413 433 100205 434 102150 435 107358 436 108363 437 112283 438 113128 439 116690 440 116301 441 119705 442 118234 443 120746 444 119105 445 120924 446 118624 447 120959 448 118462 449 119885 450 118338 451 119732 452 118325 453 121109 454 119868 455 123573 456 124649 457 128086 458 129862 459 135617 460 137804 461 143227 462 146980 463 151898 464 155619 465 163291 466 165704 467 171140 468 175066 469 178750 470 181953 471 184997 472 187308 473 188416 474 190432 475 190558 476 191588 477 191318 478 191865 479 190604 480 191394 481 190466 482 190886 483 189633 484 191492 485 191657 486 194039 487 195731 488 199567 489 202382 490 208176 491 212219 492 218615 493 224506 494 231362 495 236708 496 247453 497 251931 498 260778 499 265910 500 275151 501 278550 502 287476 503 288664 504 296246 505 296743 506 302569 507 300929 508 306239 509 303433 510 307682 511 303892 512 307163 513 303132 514 306472 515 302315 516 306095 517 304128 518 308838 519 307437 520 314789 521 315650 522 323429 523 327754 524 337830 525 342100 526 354497 527 360320 528 375702 529 382730 530 395878 531 405087 532 418426 533 426653 534 437824 535 446141 536 455361 537 462628 538 468881 539 474636 540 478704 541 482557 542 483924 543 487774 544 486662 545 488398 546 487280 547 487716 548 486115 549 487938 550 485645 551 489036 552 490743 553 493899 554 497858 555 506125 556 510504 557 520800 558 531484 559 541494 560 553023 561 572496 562 581726 563 601399 564 615879 565 634704 566 647358 567 669665 568 679470 569 700026 570 709019 571 726757 572 731991 573 749371 574 751095 575 764300 576 764590 577 774831 578 771768 579 779879 580 773927 581 781009 582 774843 583 780905 584 774417 585 782097 586 778244 587 787054 588 784079 589 798281 590 799373 591 815598 592 820972 593 841269 594 849253 595 878092 596 889385 597 917240 598 935227 599 964424 600 983590 601 1014633 602 1035242 603 1063306 604 1085454 605 1109936 606 1130138 607 1150708 608 1167640 609 1183963 610 1199210 611 1209323 612 1219996 613 1226988 614 1233894 615 1235755 616 1240420 617 1239230 618 1241976 619 1241346 620 1244050 621 1241695 622 1248582 623 1250393 624 1256940 625 1265685 626 1276868 627 1287924 628 1306023 629 1321971 630 1350157 631 1371542 632 1402484 633 1429050 634 1468113 635 1497800 636 1541029 637 1571796 638 1617357 639 1647104 640 1694502 641 1720106 642 1765445 643 1789342 644 1829490 645 1847564 646 1883326 647 1895157 648 1925938 649 1930625 650 1954590 651 1955975 652 1972675 653 1966533 654 1983378 655 1973962 656 1987363 657 1979321 658 1991371 659 1983866 660 2004246 661 1996349 662 2021780 663 2024120 664 2050999 665 2058723 666 2107101 667 2116994 668 2166918 669 2194309 670 2249913 671 2283321 672 2349538 673 2387900 674 2455067 675 2506429 676 2568654 677 2620192 678 2685521 679 2733932 680 2791567 681 2842356 682 2890812 683 2933354 684 2976004 685 3013164 686 3044144 687 3072647 688 3092652 689 3113544 690 3127389 691 3139889 692 3145174 693 3155775 694 3158702 695 3164673 696 3167553 697 3177274 698 3183624 699 3193764 700 3208508 701 3226923 702 3248175 703 3284720 704 3312034 705 3356624 706 3403000 707 3461429 708 3514105 709 3592257 710 3651615 711 3740847 712 3809287 713 3905712 714 3977808 715 4082376 716 4152789 717 4256127 718 4325818 719 4424269 720 4487451 721 4580787 722 4632752 723 4717877 724 4759466 725 4828631 726 4856258 727 4915631 728 4929395 729 4975697 730 4979182 731 5017392 732 5009032 733 5044806 734 5030271 735 5062131 736 5052600 737 5087510 738 5073609 739 5123907 740 5117382 741 5179888 742 5189704 743 5265328 744 5288411 745 5385164 746 5428543 747 5538518 748 5607314 749 5730720 750 5815228 751 5956341 752 6056416 753 6201403 754 6315976 755 6461222 756 6583026 757 6726521 758 6847186 759 6983331 760 7104217 761 7224854 762 7334356 763 7442320 764 7535405 765 7621339 766 7700989 767 7765186 768 7829258 769 7874432 770 7918625 771 7953562 772 7981896 773 8005896 774 8031641 775 8040759 776 8065173 777 8088701 778 8101351 779 8129095 780 8175618 781 8203434 782 8258494 783 8323476 784 8393446 785 8472855 786 8590116 787 8680099 788 8824644 789 8952321 790 9114973 791 9259208 792 9460804 793 9613932 794 9829719 795 10003793 796 10225730 797 10402856 798 10635767 799 10803912 800 11031486 801 11204568 802 11413101 803 11560161 804 11760870 805 11884089 806 12053528 807 12155541 808 12299299 809 12370363 810 12494412 811 12535341 812 12636492 813 12656571 814 12741714 815 12745172 816 12820962 817 12812850 818 12891053 819 12871749 820 12976954 821 12964619 822 13071653 823 13086057 824 13223969 825 13262681 826 13436383 827 13509091 828 13711981 829 13837162 830 14075233 831 14234242 832 14510280 833 14708806 834 15006640 835 15247215 836 15564615 837 15826185 838 16155359 839 16437230 840 16773641 841 17059974 842 17383606 843 17673435 844 17974060 845 18239410 846 18515100 847 18760148 848 18995880 849 19204364 850 19403698 851 19577412 852 19735346 853 19874906 854 19996154 855 20095736 856 20198662 857 20270915 858 20339876 859 20403923 860 20466990 861 20525047 862 20590530 863 20656160 864 20733326 865 20834615 866 20932814 867 21070039 868 21211883 869 21400627 870 21580073 871 21835299 872 22060436 873 22372913 874 22654623 875 23029346 876 23352878 877 23782873 878 24143886 879 24610949 880 25012956 881 25512139 882 25929948 883 26457018 884 26878440 885 27397430 886 27818585 887 28314751 888 28698718 889 29176004 890 29523930 891 29951870 892 30252301 893 30631456 894 30875442 895 31201559 896 31382595 897 31675373 898 31790827 899 32035845 900 32118371 901 32319045 902 32355770 903 32573650 904 32566697 905 32772633 906 32789522 907 32993833 908 33024516 909 33293333 910 33344085 911 33656541 912 33795903 913 34150853 914 34355138 915 34805097 916 35082189 917 35596220 918 35980257 919 36549325 920 37012685 921 37666409 922 38194989 923 38892181 924 39510622 925 40236838 926 40900465 927 41666303 928 42335058 929 43088779 930 43790949 931 44505545 932 45166579 933 45864966 934 46476576 935 47098884 936 47667004 937 48211022 938 48707297 939 49180466 940 49593015 941 49988006 942 50322918 943 50648806 944 50906720 945 51170635 946 51393548 947 51601576 948 51774685 949 51974511 950 52142028 951 52326780 952 52534932 953 52737691 954 52990366 955 53249287 956 53584241 957 53901138 958 54357709 959 54759516 960 55313571 961 55836308 962 56514488 963 57135312 964 57938593 965 58656857 966 59571662 967 60411133 968 61425888 969 62353968 970 63454427 971 64438990 972 65596907 973 66607839 974 67774250 975 68810474 976 69970781 977 70950731 978 72085372 979 73019524 980 74070421 981 74914823 982 75891951 983 76632022 984 77498511 985 78130500 986 78907914 987 79388785 988 80083924 989 80444302 990 81042660 991 81323119 992 81842503 993 82012453 994 82526787 995 82652347 996 83135267 997 83265118 998 83783030 999 83942724 1000 84527031 1001 84756678 1002 85431770 1003 85797857 1004 86579177 1005 87074331 1006 88012667 1007 88678778 1008 89750169 1009 90603384 1010 91828937 1011 92856504 1012 94261396 1013 95458060 1014 96980273 1015 98363401 1016 99987158 1017 101468855 1018 103206549 1019 104752428 1020 106489540 1021 108122073 1022 109841781 1023 111437889 1024 113137703 1025 114675453 1026 116279965 1027 117719904 1028 119206442 1029 120531196 1030 121867320 1031 123031070 1032 124230523 1033 125218948 1034 126247035 1035 127118791 1036 127949368 1037 128661301 1038 129411165 1039 129971329 1040 130598128 1041 131142881 1042 131659174 1043 132181077 1044 132716572 1045 133246337 1046 133808111 1047 134476195 1048 135064764 1049 135879323 1050 136667741 1051 137625114 1052 138560870 1053 139779739 1054 140897261 1055 142345470 1056 143720124 1057 145417091 1058 147025362 1059 149013790 1060 150850798 1061 153048983 1062 155130896 1063 157497906 1064 159735581 1065 162314176 1066 164641834 1067 167291959 1068 169747473 1069 172401341 1070 174823618 1071 177520282 1072 179849461 1073 182449640 1074 184688924 1075 187149582 1076 189211341 1077 191511601 1078 193338794 1079 195449921 1080 197032441 1081 198955985 1082 200263441 1083 201949704 1084 203023375 1085 204533979 1086 205364414 1087 206747763 1088 207398315 1089 208652388 1090 209234651 1091 210441989 1092 210954074 1093 212220479 1094 212789273 1095 214113665 1096 214829703 1097 216311811 1098 217220471 1099 218935495 1100 220124218 1101 222063192 1102 223579848 1103 225856731 1104 227751332 1105 230338804 1106 232621316 1107 235599135 1108 238246628 1109 241511236 1110 244547763 1111 248083768 1112 251403959 1113 255211296 1114 258736750 1115 262690520 1116 266421570 1117 270443551 1118 274213091 1119 278250446 1120 282023260 1121 285962798 1122 289595630 1123 293403272 1124 296855650 1125 300414189 1126 303631164 1127 306903054 1128 309781717 1129 312759629 1130 315309411 1131 317913413 1132 320164508 1133 322430887 1134 324337576 1135 326330617 1136 328024351 1137 329716211 1138 331269274 1139 332783573 1140 334264671 1141 335687546 1142 337200752 1143 338640915 1144 340302882 1145 341854496 1146 343727062 1147 345520315 1148 347711331 1149 349795763 1150 352409599 1151 354934619 1152 357993434 1153 361053738 1154 364650518 1155 368131712 1156 372321163 1157 376351949 1158 380978059 1159 385563329 1160 390673198 1161 395648151 1162 401252402 1163 406551810 1164 412414239 1165 418075943 1166 424122727 1167 429862060 1168 436075023 1169 441835257 1170 448021235 1171 453657167 1172 459729079 1173 465151069 1174 470948699 1175 476036782 1176 481558905 1177 486136217 1178 491265088 1179 495383884 1180 500047615 1181 503631107 1182 507934651 1183 510911542 1184 514798803 1185 517398493 1186 520866434 1187 523049551 1188 526341896 1189 528223511 1190 531285828 1191 533120209 1192 536102565 1193 537961615 1194 541086687 1195 543046836 1196 546408072 1197 548749236 1198 552416562 1199 555244495 1200 559471992 1201 562852648 1202 567696902 1203 571909822 1204 577367519 1205 582298257 1206 588574461 1207 594260358 1208 601226501 1209 607798908 1210 615375596 1211 622625551 1212 630964052 1213 638752356 1214 647554019 1215 655952891 1216 665094143 1217 673767626 1218 683210911 1219 692019231 1220 701504902 1221 710387508 1222 719708831 1223 728376511 1224 737468038 1225 745772904 1226 754447060 1227 762241554 1228 770333906 1229 777540506 1230 784965749 1231 791537193 1232 798252061 1233 804143093 1234 810155650 1235 815440006 1236 820712596 1237 825536467 1238 830206363 1239 834554748 1240 838861615 1241 842968440 1242 846869813 1243 850972529 1244 854822453 1245 858943747 1246 862916538 1247 867384740 1248 871679851 1249 876692193 1250 881542515 1251 887319792 1252 892939390 1253 899539967 1254 906145110 1255 913735049 1256 921319116 1257 930076594 1258 938742069 1259 948557783 1260 958431865 1261 969301077 1262 980151571 1263 992139776 1264 1003910051 1265 1016733599 1266 1029339649 1267 1042914584 1268 1056095899 1269 1070186650 1270 1083760341 1271 1098146576 1272 1111786788 1273 1126310210 1274 1139817371 1275 1154086905 1276 1167224467 1277 1181093037 1278 1193522499 1279 1206879465 1280 1218433752 1281 1231015261 1282 1241618086 1283 1253366298 1284 1262864166 1285 1273734469 1286 1282185642 1287 1292143169 1288 1299633625 1289 1308742839 1290 1315359403 1291 1323822863 1292 1329793997 1293 1337672810 1294 1343204828 1295 1350826819 1296 1356201378 1297 1363760107 1298 1369273611 1299 1377044102 1300 1383113838 1301 1391447866 1302 1398228093 1303 1407539816 1304 1415361738 1305 1425634994 1306 1434945320 1307 1446510660 1308 1457120308 1309 1470405308 1310 1482588945 1311 1497197049 1312 1511282020 1313 1527456288 1314 1543012026 1315 1560865381 1316 1577906214 1317 1597015935 1318 1615531999 1319 1635805946 1320 1655320433 1321 1676680764 1322 1696997152 1323 1718912879 1324 1739721062 1325 1761923671 1326 1782901805 1327 1805028956 1328 1825687447 1329 1847450311 1330 1867504179 1331 1888476171 1332 1907726611 1333 1927569990 1334 1945757563 1335 1964428147 1336 1981251113 1337 1998441748 1338 2014166015 1339 2029685090 1340 2044101854 1341 2058327353 1342 2071457188 1343 2084263189 1344 2096466239 1345 2108170490 1346 2119542958 1347 2130375819 1348 2141245158 1349 2151624277 1350 2162387084 1351 2172671907 1352 2183765802 1353 2194510562 1354 2206268857 1355 2217884591 1356 2230866731 1357 2243625291 1358 2258063782 1359 2272680905 1360 2288859681 1361 2305306819 1362 2323852200 1363 2342390685 1364 2363066567 1365 2384156072 1366 2407041085 1367 2430423606 1368 2455872100 1369 2481328602 1370 2508948152 1371 2536738245 1372 2566198516 1373 2595681818 1374 2627035931 1375 2657930072 1376 2690512081 1377 2722448599 1378 2755892786 1379 2788216192 1380 2822113504 1381 2854343793 1382 2888168999 1383 2919775243 1384 2953109276 1385 2983595763 1386 3015908013 1387 3044950888 1388 3075904462 1389 3103038789 1390 3132479669 1391 3157676701 1392 3185083991 1393 3208242190 1394 3233821381 1395 3254855753 1396 3278654571 1397 3297735737 1398 3319725083 1399 3337324960 1400 3357904448 1401 3374087182 1402 3393660680 1403 3409181620 1404 3428186326 1405 3443424096 1406 3462532819 1407 3478357843 1408 3497939559 1409 3514789231 1410 3535759583 1411 3554128062 1412 3576882986 1413 3597669577 1414 3622576130 1415 3645939546 1416 3673908825 1417 3700253932 1418 3731233547 1419 3761097288 1420 3795328297 1421 3828536998 1422 3866351639 1423 3902894955 1424 3943968419 1425 3983963261 1426 4028167069 1427 4071052698 1428 4117984243 1429 4163541357 1430 4212827132 1431 4260191886 1432 4311230474 1433 4360001417 1434 4411901170 1435 4461435863 1436 4513666770 1437 4562914353 1438 4614827846 1439 4663463723 1440 4714085939 1441 4761457558 1442 4810240452 1443 4855809706 1444 4902161316 1445 4945502483 1446 4989238535 1447 5030048687 1448 5070664849 1449 5108898040 1450 5146515087 1451 5182106025 1452 5216667609 1453 5249831710 1454 5281838541 1455 5312722359 1456 5342523732 1457 5372006615 1458 5400153094 1459 5428638281 1460 5456094785 1461 5484253971 1462 5511931333 1463 5540720914 1464 5569039308 1465 5599577817 1466 5629718025 1467 5662202139 1468 5695446276 1469 5731010389 1470 5767200294 1471 5806957402 1472 5847239093 1473 5890919864 1474 5936135013 1475 5984564041 1476 6034313529 1477 6088097396 1478 6142830231 1479 6201359786 1480 6261213595 1481 6324759920 1482 6389096510 1483 6457136763 1484 6525778834 1485 6597633824 1486 6669664105 1487 6744937250 1488 6819456065 1489 6897182694 1490 6973257487 1491 7052731890 1492 7129102646 1493 7209173317 1494 7285206881 1495 7364632215 1496 7439169910 1497 7517533580 1498 7589614740 1499 7665594303 1500 7734760269