1 0
2 1
3 4
4 6
5 5
6 7
7 13
8 13
9 9
10 10
11 16
12 21
13 19
14 14
15 22
16 28
17 20
18 21
19 29
20 31
21 33
22 34
23 35
24 39
25 31
26 25
27 42
28 51
29 42
30 37
31 53
32 56
33 48
34 44
35 37
36 60
37 64
38 49
39 60
40 68
41 53
42 60
43 80
44 62
45 69
46 71
47 73
48 93
49 73
50 54
51 73
52 96
53 81
54 81
55 95
56 95
57 102
58 97
59 78
60 90
61 104
62 79
63 108
64 125
65 83
66 96
67 125
68 109
69 117
70 119
71 108
72 147
73 128
74 92
75 114
76 142
77 128
78 127
79 150
80 125
81 138
82 143
83 125
84 150
85 161
86 120
87 156
88 197
89 122
90 129
91 173
92 170
93 186
94 158
95 131
96 189
97 190
98 131
99 159
100 182
101 156
102 186
103 211
104 176
105 183
106 201
107 173
108 213
109 219
110 150
111 202
112 260
113 195
114 189
115 216
116 177
117 231
118 241
119 192
120 246
121 234
122 187
123 237
124 247
125 191
126 210
127 279
128 245
129 237
130 242
131 195
132 273
133 294
134 210
135 234
136 296
137 237
138 249
139 279
140 221
141 282
142 299
143 235
144 291
145 278
146 202
147 294
148 349
149 248
150 256
151 325
152 281
153 312
154 304
155 248
156 309
157 365
158 267
159 285
160 350
161 246
162 315
163 365
164 279
165 321
166 336
167 287
168 387
169 356
170 248
171 315
172 400
173 322
174 315
175 375
176 334
177 393
178 372
179 283
180 342
181 392
182 311
183 396
184 427
185 299
186 345
187 434
188 350
189 396
190 410
191 330
192 462
193 437
194 277
195 328
196 451
197 379
198 417
199 435
200 372
201 411
202 458
203 374
204 417
205 472
206 327
207 453
208 527
209 360
210 393
211 485
212 412
213 489
214 480
215 357
216 477
217 523
218 380
219 435
220 479
221 384
222 441
223 531
224 428
225 477
226 496
227 395
228 534
229 516
230 365
231 468
232 641
233 437
234 444
235 546
236 431
237 549
238 557
239 431
240 561
241 558
242 428
243 513
244 545
245 458
246 496
247 626
248 516
249 543
250 534
251 423
252 603
253 686
254 449
255 492
256 655
257 491
258 543
259 573
260 460
261 576
262 649
263 516
264 621
265 623
266 451
267 624
268 704
269 479
270 531
271 631
272 573
273 666
274 631
275 493
276 600
277 743
278 521
279 603
280 743
281 533
282 630
283 734
284 535
285 621
286 637
287 554
288 762
289 682
290 482
291 618
292 786
293 585
294 615
295 725
296 592
297 732
298 780
299 525
300 666
301 788
302 603
303 703
304 778
305 578
306 621
307 789
308 647
309 741
310 772
311 585
312 816
313 830
314 517
315 645
316 810
317 708
318 711
319 794
320 639
321 702
322 838
323 642
324 732
325 794
326 603
327 774
328 937
329 631
330 720
331 869
332 683
333 849
334 809
335 619
336 840
337 924
338 660
339 717
340 868
341 631
342 792
343 963
344 745
345 837
346 849
347 714
348 837
349 883
350 626
351 777
352 1041
353 707
354 765
355 857
356 693
357 936
358 984
359 693
360 870
361 951
362 706
363 861
364 916
365 740
366 823
367 1019
368 830
369 843
370 886
371 715
372 993
373 1080
374 691
375 864
376 1021
377 802
378 930
379 1016
380 763
381 897
382 1057
383 777
384 954
385 1015
386 746
387 933
388 1070
389 769
390 828
391 981
392 907
393 1029
394 1026
395 740
396 960
397 1158
398 826
399 912
400 1171
401 827
402 963
403 1154
404 756
405 984
406 1033
407 914
408 1143
409 1059
410 787
411 963
412 1184
413 905
414 951
415 1107
416 868
417 1104
418 1147
419 795
420 984
421 1160
422 937
423 1080
424 1182
425 830
426 963
427 1250
428 966
429 1059
430 1136
431 878
432 1194
433 1215
434 842
435 1030
436 1210
437 972
438 1140
439 1150
440 908
441 1083
442 1285
443 1003
444 1059
445 1267
446 828
447 1119
448 1403
449 932
450 1047
451 1167
452 1037
453 1224
454 1218
455 913
456 1218
457 1396
458 930
459 1092
460 1255
461 953
462 1215
463 1456
464 1006
465 1146
466 1303
467 1009
468 1200
469 1291
470 991
471 1197
472 1452
473 1099
474 1122
475 1282
476 988
477 1335
478 1429
479 986
480 1281
481 1263
482 1037
483 1254
484 1360
485 1025
486 1140
487 1506
488 1189
489 1242
490 1329
491 1029
492 1371
493 1493
494 1002
495 1182
496 1451
497 1134
498 1341
499 1445
500 1080
501 1299
502 1454
503 1102
504 1383
505 1510
506 1049
507 1335
508 1552
509 1094
510 1183
511 1465
512 1249
513 1440
514 1389
515 1086
516 1278
517 1597
518 1185
519 1317
520 1618
521 1071
522 1440
523 1569
524 1078
525 1377
526 1488
527 1200
528 1536
529 1528
530 1060
531 1314
532 1693
533 1308
534 1338
535 1479
536 1218
537 1509
538 1625
539 1133
540 1416
541 1601
542 1175
543 1485
544 1612
545 1139
546 1296
547 1737
548 1332
549 1395
550 1582
551 1180
552 1614
553 1789
554 1198
555 1413
556 1581
557 1339
558 1452
559 1557
560 1306
561 1503
562 1727
563 1269
564 1500
565 1700
566 1168
567 1572
568 1923
569 1236
570 1395
571 1662
572 1357
573 1605
574 1626
575 1245
576 1608
577 1796
578 1302
579 1380
580 1678
581 1318
582 1608
583 1869
584 1274
585 1557
586 1641
587 1394
588 1713
589 1789
590 1294
591 1474
592 2036
593 1369
594 1437
595 1765
596 1354
597 1800
598 1871
599 1340
600 1650
601 1737
602 1356
603 1740
604 1835
605 1390
606 1605
607 1885
608 1499
609 1623
610 1831
611 1276
612 1707
613 2015
614 1306
615 1533
616 1945
617 1586
618 1722
619 1789
620 1381
621 1647
622 1920
623 1505
624 1773
625 1967
626 1279
627 1791
628 2032
629 1381
630 1617
631 1975
632 1680
633 1836
634 1856
635 1362
636 1698
637 2110
638 1542
639 1728
640 2022
641 1435
642 1785
643 2040
644 1500
645 1812
646 1932
647 1513
648 2031
649 1910
650 1391
651 1707
652 2285
653 1690
654 1653
655 2037
656 1522
657 1965
658 2135
659 1479
660 1830
661 2020
662 1605
663 1866
664 2034
665 1558
666 1770
667 2208
668 1635
669 1932
670 1975
671 1469
672 2094
673 2269
674 1496
675 1731
676 2098
677 1648
678 1912
679 2047
680 1715
681 1932
682 2220
683 1750
684 1824
685 2193
686 1550
687 2052
688 2426
689 1538
690 1824
691 2149
692 1734
693 2142
694 2198
695 1635
696 1995
697 2414
698 1619
699 1806
700 2248
701 1645
702 2079
703 2291
704 1761
705 1902
706 2053
707 1742
708 2244
709 2327
710 1579
711 1899
712 2430
713 1791
714 1842
715 2278
716 1723
717 2166
718 2450
719 1602
720 2124
721 2278
722 1802
723 2181
724 2227
725 1774
726 1941
727 2442
728 1893
729 2103
730 2302
731 1653
732 2253
733 2493
734 1622
735 2013
736 2478
737 1906
738 2133
739 2318
740 1712
741 2088
742 2545
743 1923
744 2178
745 2364
746 1717
747 2172
748 2575
749 1799
750 2061
751 2404
752 1995
753 2385
754 2206
755 1678
756 2133
757 2757
758 1932
759 2091
760 2671
761 1766
762 2232
763 2656
764 1863
765 2229
766 2311
767 1945
768 2487
769 2364
770 1743
771 2149
772 2784
773 2022
774 2184
775 2450
776 1861
777 2469
778 2698
779 1859
780 2160
781 2586
782 1949
783 2286
784 2616
785 2007
786 2208
787 2636
788 2065
789 2220
790 2497
791 1884
792 2631
793 2836
794 1770
795 2277
796 2513
797 2063
798 2409
799 2612
800 2060
801 2250
802 2763
803 1993
804 2334
805 2680
806 1936
807 2532
808 2954
809 1951
810 2142
811 2549
812 2194
813 2691
814 2673
815 1926
816 2424
817 2883
818 1991
819 2268
820 2713
821 2053
822 2439
823 2950
824 2025
825 2427
826 2698
827 2218
828 2661
829 2653
830 2083
831 2283
832 2943
833 2133
834 2388
835 2720
836 1977
837 2793
838 2899
839 1967
840 2667
841 2804
842 2152
843 2541
844 2766
845 2061
846 2289
847 3036
848 2386
849 2496
850 2703
851 2091
852 2700
853 3039
854 2011
855 2514
856 3051
857 2261
858 2592
859 2809
860 2130
861 2604
862 3142
863 2331
864 2604
865 2955
866 1971
867 2613
868 3133
869 2210
870 2587
871 2751
872 2458
873 2814
874 2753
875 2078
876 2622
877 3311
878 2299
879 2565
880 3032
881 2099
882 2724
883 3233
884 2178
885 2652
886 2979
887 2289
888 2910
889 3029
890 2211
891 2664
892 3174
893 2431
894 2514
895 3029
896 2332
897 2907
898 3202
899 2069
900 2745
901 2917
902 2364
903 2880
904 3221
905 2380
906 2556
907 3382
908 2393
909 2640
910 3025
911 2347
912 3186
913 3343
914 2201
915 2565
916 3064
917 2565
918 2997
919 3047
920 2332
921 2838
922 3232
923 2399
924 2751
925 3361
926 2243
927 2883
928 3672
929 2301
930 2610
931 3082
932 2620
933 3180
934 3009
935 2340
936 2871
937 3390
938 2540
939 2802
940 3295
941 2319
942 3057
943 3362
944 2407
945 2913
946 3220
947 2678
948 3015
949 3312
950 2308
951 2784
952 3621
953 2594
954 2769
955 3303
956 2477
957 3162
958 3432
959 2389
960 3162
961 3284
962 2451
963 3063
964 3172
965 2416
966 2865
967 3656
968 2876
969 2958
970 3393
971 2337
972 3192
973 3749
974 2448
975 2890
976 3373
977 2780
978 2979
979 3191
980 2575
981 3108
982 3760
983 2674
984 3213
985 3331
986 2328
987 3153
988 3823
989 2590
990 2874
991 3503
992 2779
993 3342
994 3355
995 2589
996 3042
997 3681
998 2748
999 2898
1000 3546