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