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