1 0
2 1
3 2
4 2
5 3
6 4
7 5
8 4
9 5
10 4
11 7
12 7
13 7
14 8
15 10
16 8
17 10
18 9
19 11
20 13
21 14
22 12
23 17
24 14
25 14
26 13
27 16
28 16
29 20
30 19
31 20
32 21
33 22
34 17
35 22
36 23
37 22
38 26
39 28
40 25
41 31
42 24
43 27
44 31
45 32
46 28
47 37
48 32
49 33
50 34
51 33
52 35
53 39
54 38
55 41
56 44
57 46
58 35
59 45
60 43
61 43
62 46
63 48
64 45
65 55
66 45
67 46
68 56
69 53
70 51
71 62
72 56
73 58
74 57
75 57
76 57
77 66
78 61
79 66
80 69
81 69
82 58
83 72
84 69
85 68
86 76
87 75
88 73
89 85
90 67
91 71
92 87
93 82
94 75
95 91
96 80
97 85
98 82
99 79
100 85
101 95
102 88
103 90
104 102
105 99
106 90
107 101
108 96
109 100
110 107
111 105
112 100
113 122
114 98
115 102
116 117
117 112
118 105
119 125
120 114
121 121
122 118
123 112
124 116
125 127
126 115
127 124
128 137
129 131
130 117
131 134
132 128
133 129
134 142
135 132
136 135
137 156
138 129
139 133
140 153
141 148
142 139
143 160
144 141
145 149
146 153
147 143
148 153
149 169
150 149
151 160
152 172
153 166
154 152
155 176
156 165
157 168
158 178
159 167
160 168
161 193
162 160
163 167
164 197
165 178
166 176
167 200
168 178
169 194
170 191
171 176
172 190
173 213
174 186
175 195
176 218
177 206
178 190
179 213
180 196
181 208
182 220
183 211
184 213
185 240
186 198
187 207
188 233
189 219
190 217
191 248
192 221
193 236
194 236
195 204
196 229
197 250
198 229
199 237
200 265
201 250
202 231
203 257
204 243
205 252
206 267
207 251
208 254
209 291
210 233
211 256
212 287
213 263
214 261
215 292
216 261
217 287
218 283
219 261
220 270
221 299
222 262
223 279
224 305
225 286
226 278
227 301
228 286
229 293
230 312
231 288
232 310
233 341
234 280
235 290
236 337
237 307
238 304
239 350
240 302
241 337
242 331
243 294
244 321
245 347
246 314
247 334
248 364
249 350
250 320
251 352
252 327
253 350
254 374
255 329
256 355
257 395
258 323
259 337
260 386
261 357
262 357
263 396
264 356
265 381
266 386
267 349
268 376
269 407
270 354
271 384
272 414
273 391
274 380
275 414
276 379
277 405
278 418
279 387
280 396
281 471
282 381
283 399
284 451
285 393
286 406
287 442
288 411
289 445
290 434
291 389
292 436
293 459
294 409
295 426
296 483
297 449
298 437
299 472
300 422
301 461
302 484
303 444
304 463
305 508
306 425
307 449
308 502
309 473
310 465
311 519
312 460
313 512
314 499
315 438
316 493
317 534
318 463
319 489
320 526
321 495
322 480
323 521
324 486
325 499
326 556
327 489
328 522
329 584
330 479
331 512
332 565
333 519
334 526
335 568
336 512
337 570
338 567
339 496
340 537
341 588
342 511
343 552
344 614
345 560
346 549
347 601
348 537
349 575
350 586
351 547
352 588
353 646
354 542
355 547
356 633
357 559
358 592
359 642
360 562
361 641
362 627
363 559
364 603
365 651
366 581
367 619
368 667
369 622
370 595
371 648
372 607
373 652
374 676
375 598
376 650
377 716
378 586
379 642
380 704
381 641
382 656
383 701
384 626
385 676
386 702
387 608
388 673
389 725
390 618
391 674
392 735
393 692
394 690
395 712
396 663
397 708
398 744
399 661
400 703
401 806
402 658
403 705
404 772
405 672
406 715
407 794
408 701
409 780
410 763
411 684
412 744
413 784
414 707
415 731
416 812
417 754
418 739
419 791
420 701
421 788
422 817
423 724
424 786
425 851
426 723
427 762
428 855
429 769
430 774
431 867
432 757
433 836
434 835
435 732
436 832
437 874
438 768
439 821
440 865
441 816
442 822
443 882
444 791
445 836
446 899
447 793
448 855
449 951
450 769
451 829
452 930
453 826
454 864
455 897
456 836
457 935
458 918
459 821
460 867
461 965
462 823
463 906
464 985
465 862
466 907
467 947
468 851
469 922
470 974
471 885
472 942
473 1039
474 855
475 902
476 990
477 901
478 952
479 1026
480 885
481 1000
482 991
483 866
484 977
485 1008
486 907
487 978
488 1053
489 960
490 938
491 1051
492 944
493 1007
494 1058
495 911
496 1016
497 1111
498 943
499 1001
500 1070
501 983
502 1024
503 1095
504 971
505 1076
506 1100
507 957
508 1057
509 1120
510 939
511 1037
512 1140
513 1052
514 1050
515 1099
516 1015
517 1082
518 1125
519 1019
520 1081
521 1202
522 1010
523 1085
524 1184
525 1018
526 1111
527 1191
528 1040
529 1182
530 1146
531 1024
532 1126
533 1205
534 1072
535 1110
536 1244
537 1119
538 1140
539 1196
540 1061
541 1192
542 1225
543 1089
544 1171
545 1254
546 1059
547 1169
548 1265
549 1119
550 1157
551 1268
552 1123
553 1251
554 1282
555 1093
556 1231
557 1298
558 1120
559 1206
560 1268
561 1213
562 1222
563 1292
564 1175
565 1226
566 1311
567 1158
568 1285
569 1413
570 1120
571 1245
572 1354
573 1201
574 1259
575 1323
576 1211
577 1334
578 1348
579 1171
580 1273
581 1382
582 1220
583 1305
584 1400
585 1242
586 1306
587 1371
588 1229
589 1371
590 1394
591 1246
592 1369
593 1463
594 1225
595 1271
596 1475
597 1309
598 1362
599 1479
600 1255
601 1455
602 1417
603 1279
604 1412
605 1451
606 1304
607 1402
608 1484
609 1349
610 1364
611 1481
612 1319
613 1452
614 1510
615 1281
616 1431
617 1594
618 1328
619 1419
620 1509
621 1380
622 1457
623 1538
624 1382
625 1493
626 1548
627 1334
628 1489
629 1583
630 1321
631 1506
632 1624
633 1455
634 1505
635 1544
636 1408
637 1525
638 1605
639 1422
640 1511
641 1703
642 1390
643 1501
644 1638
645 1427
646 1564
647 1632
648 1473
649 1638
650 1590
651 1422
652 1607
653 1715
654 1462
655 1550
656 1708
657 1540
658 1568
659 1697
660 1474
661 1652
662 1711
663 1486
664 1640
665 1708
666 1518
667 1634
668 1753
669 1573
670 1603
671 1738
672 1524
673 1753
674 1759
675 1462
676 1693
677 1779
678 1551
679 1661
680 1781
681 1658
682 1687
683 1779
684 1592
685 1701
686 1802
687 1615
688 1763
689 1906
690 1548
691 1720
692 1854
693 1635
694 1764
695 1846
696 1642
697 1853
698 1837
699 1617
700 1730
701 1928
702 1650
703 1777
704 1934
705 1668
706 1791
707 1844
708 1701
709 1862
710 1869
711 1691
712 1849
713 1987
714 1658
715 1752
716 1996
717 1758
718 1870
719 1968
720 1669
721 1932
722 1962
723 1706
724 1898
725 1986
726 1734
727 1895
728 1978
729 1858
730 1848
731 1994
732 1800
733 1952
734 2039
735 1695
736 1980
737 2109
738 1763
739 1911
740 2026
741 1827
742 1945
743 2089
744 1857
745 2007
746 2082
747 1785
748 1988
749 2113
750 1802
751 2016
752 2129
753 1929
754 1997
755 2038
756 1858
757 2091
758 2157
759 1891
760 2013
761 2251
762 1849
763 2010
764 2211
765 1896
766 2070
767 2200
768 1927
769 2163
770 2080
771 1892
772 2150
773 2220
774 1943
775 2031
776 2266
777 2021
778 2134
779 2221
780 1902
781 2199
782 2238
783 1960
784 2152
785 2301
786 1989
787 2127
788 2322
789 2047
790 2109
791 2291
792 2038
793 2305
794 2314
795 1944
796 2219
797 2336
798 2000
799 2223
800 2322
801 2131
802 2233
803 2300
804 2073
805 2189
806 2404
807 2079
808 2300
809 2499
810 2004
811 2233
812 2386
813 2181
814 2302
815 2350
816 2145
817 2403
818 2376
819 2048
820 2285
821 2521
822 2136
823 2358
824 2489
825 2152
826 2313
827 2474
828 2194
829 2407
830 2445
831 2181
832 2394
833 2539
834 2179
835 2290
836 2541
837 2235
838 2420
839 2545
840 2152
841 2548
842 2548
843 2191
844 2480
845 2506
846 2235
847 2412
848 2618
849 2373
850 2364
851 2570
852 2271
853 2536
854 2593
855 2239
856 2546
857 2727
858 2263
859 2462
860 2598
861 2346
862 2558
863 2683
864 2347
865 2569
866 2657
867 2263
868 2545
869 2732
870 2295
871 2555
872 2740
873 2453
874 2566
875 2574
876 2429
877 2690
878 2726
879 2420
880 2547
881 2843
882 2343
883 2587
884 2813
885 2380
886 2685
887 2810
888 2451
889 2755
890 2724
891 2421
892 2700
893 2857
894 2456
895 2602
896 2837
897 2565
898 2716
899 2794
900 2434
901 2749
902 2835
903 2450
904 2809
905 2923
906 2506
907 2731
908 2909
909 2580
910 2642
911 2970
912 2589
913 2894
914 2935
915 2422
916 2815
917 2914
918 2565
919 2844
920 2916
921 2737
922 2816
923 2931
924 2572
925 2825
926 3023
927 2604
928 2913
929 3127
930 2512
931 2785
932 3079
933 2696
934 2909
935 2955
936 2663
937 3032
938 2996
939 2642
940 2877
941 3140
942 2695
943 2927
944 3111
945 2679
946 2960
947 3070
948 2725
949 3035
950 3025
951 2718
952 2989
953 3251
954 2740
955 2873
956 3221
957 2795
958 3023
959 3165
960 2720
961 3177
962 3128
963 2745
964 3085
965 3118
966 2763
967 3085
968 3265
969 2914
970 2998
971 3190
972 2843
973 3124
974 3315
975 2754
976 3155
977 3391
978 2819
979 3063
980 3174
981 2961
982 3188
983 3316
984 2937
985 3193
986 3305
987 2819
988 3220
989 3416
990 2801
991 3223
992 3391
993 3026
994 3148
995 3252
996 2996
997 3292
998 3416
999 2933
1000 3175