1 1
2 0
3 1
4 1
5 0
6 1
7 1
8 0
9 1
10 2
11 1
12 0
13 1
14 1
15 1
16 2
17 1
18 1
19 2
20 1
21 2
22 2
23 0
24 2
25 3
26 1
27 1
28 3
29 2
30 1
31 4
32 3
33 0
34 3
35 3
36 2
37 4
38 3
39 3
40 3
41 2
42 3
43 3
44 2
45 4
46 6
47 4
48 2
49 5
50 4
51 2
52 6
53 5
54 3
55 7
56 6
57 3
58 5
59 5
60 5
61 6
62 5
63 4
64 7
65 7
66 6
67 8
68 6
69 5
70 9
71 7
72 4
73 9
74 9
75 6
76 10
77 9
78 4
79 9
80 10
81 8
82 11
83 11
84 9
85 10
86 10
87 9
88 10
89 10
90 9
91 14
92 14
93 7
94 14
95 14
96 7
97 15
98 15
99 8
100 15
101 17
102 13
103 13
104 15
105 15
106 14
107 16
108 14
109 17
110 19
111 14
112 20
113 19
114 11
115 22
116 21
117 12
118 19
119 23
120 19
121 20
122 23
123 20
124 19
125 23
126 21
127 21
128 24
129 21
130 28
131 26
132 17
133 27
134 27
135 18
136 31
137 33
138 21
139 28
140 33
141 24
142 27
143 33
144 27
145 30
146 36
147 30
148 29
149 34
150 30
151 36
152 39
153 28
154 35
155 41
156 30
157 40
158 44
159 31
160 41
161 46
162 33
163 35
164 46
165 41
166 40
167 50
168 42
169 38
170 50
171 43
172 46
173 53
174 45
175 55
176 53
177 39
178 53
179 55
180 44
181 56
182 62
183 48
184 49
185 66
186 55
187 50
188 68
189 60
190 57
191 69
192 58
193 60
194 66
195 59
196 72
197 71
198 55
199 70
200 80
201 63
202 71
203 85
204 66
205 68
206 90
207 73
208 67
209 87
210 80
211 78
212 89
213 76
214 80
215 92
216 79
217 91
218 99
219 80
220 92
221 105
222 84
223 86
224 106
225 94
226 90
227 114
228 101
229 90
230 114
231 103
232 96
233 115
234 104
235 111
236 125
237 106
238 113
239 122
240 109
241 119
242 130
243 113
244 118
245 142
246 123
247 115
248 143
249 125
250 122
251 152
252 132
253 127
254 149
255 140
256 144
257 154
258 138
259 144
260 158
261 141
262 150
263 173
264 147
265 153
266 187
267 153
268 142
269 184
270 164
271 153
272 195
273 180
274 160
275 186
276 181
277 175
278 191
279 181
280 191
281 209
282 184
283 189
284 213
285 187
286 191
287 229
288 199
289 184
290 236
291 220
292 194
293 235
294 226
295 211
296 237
297 225
298 220
299 240
300 234
301 241
302 255
303 231
304 234
305 270
306 242
307 236
308 288
309 258
310 246
311 298
312 265
313 245
314 291
315 277
316 263
317 297
318 289
319 275
320 304
321 296
322 288
323 318
324 295
325 295
326 343
327 307
328 299
329 350
330 315
331 307
332 362
333 330
334 304
335 367
336 361
337 321
338 366
339 365
340 339
341 382
342 370
343 352
344 390
345 375
346 375
347 413
348 375
349 369
350 431
351 398
352 368
353 438
354 423
355 387
356 453
357 442
358 396
359 444
360 452
361 428
362 459
363 453
364 446
365 483
366 455
367 449
368 505
369 464
370 457
371 538
372 494
373 456
374 534
375 517
376 476
377 543
378 539
379 490
380 546
381 559
382 518
383 562
384 553
385 535
386 600
387 562
388 542
389 617
390 580
391 564
392 641
393 602
394 556
395 640
396 641
397 576
398 652
399 668
400 602
401 670
402 676
403 616
404 678
405 685
406 663
407 712
408 686
409 677
410 736
411 703
412 684
413 759
414 731
415 694
416 790
417 773
418 693
419 791
420 804
421 723
422 802
423 815
424 753
425 822
426 836
427 804
428 848
429 822
430 819
431 892
432 845
433 824
434 925
435 888
436 836
437 946
438 926
439 826
440 945
441 976
442 871
443 964
444 993
445 918
446 991
447 993
448 952
449 1016
450 996
451 987
452 1065
453 1028
454 987
455 1094
456 1079
457 985
458 1105
459 1124
460 1012
461 1141
462 1171
463 1048
464 1148
465 1178
466 1103
467 1175
468 1177
469 1137
470 1219
471 1217
472 1176
473 1246
474 1236
475 1188
476 1296
477 1285
478 1185
479 1317
480 1341
481 1235
482 1354
483 1368
484 1251
485 1365
486 1397
487 1307
488 1396
489 1422
490 1369
491 1449
492 1438
493 1386
494 1474
495 1467
496 1419
497 1543
498 1532
499 1418
500 1572
501 1589
502 1434
503 1593
504 1637
505 1482
506 1626
507 1675
508 1551
509 1640
510 1689
511 1636
512 1692
513 1696
514 1651
515 1744
516 1756
517 1678
518 1808
519 1815
520 1675
521 1858
522 1878
523 1683
524 1866
525 1953
526 1796
527 1900
528 1959
529 1853
530 1920
531 1985
532 1927
533 1980
534 2016
535 1967
536 2076
537 2060
538 1948
539 2126
540 2138
541 1987
542 2183
543 2207
544 2021
545 2200
546 2277
547 2101
548 2217
549 2304
550 2180
551 2276
552 2348
553 2248
554 2330
555 2379
556 2299
557 2416
558 2425
559 2302
560 2476
561 2519
562 2350
563 2538
564 2584
565 2384
566 2587
567 2665
568 2447
569 2598
570 2719
571 2562
572 2655
573 2750
574 2625
575 2704
576 2803
577 2693
578 2790
579 2857
580 2740
581 2909
582 2927
583 2729
584 2954
585 3013
586 2808
587 3015
588 3104
589 2889
590 3027
591 3175
592 2986
593 3051
594 3214
595 3102
596 3175
597 3266
598 3137
599 3259
600 3305
601 3183
602 3390
603 3400
604 3199
605 3445
606 3527
607 3283
608 3476
609 3617
610 3378
611 3520
612 3696
613 3475
614 3563
615 3737
616 3608
617 3708
618 3781
619 3628
620 3794
621 3856
622 3683
623 3909
624 3985
625 3750
626 3985
627 4094
628 3790
629 3991
630 4201
631 3951
632 4080
633 4287
634 4064
635 4144
636 4336
637 4156
638 4241
639 4391
640 4247
641 4409
642 4485
643 4285
644 4500
645 4592
646 4372
647 4594
648 4704
649 4426
650 4646
651 4870
652 4570
653 4693
654 4950
655 4690
656 4793
657 5018
658 4796
659 4904
660 5083
661 4947
662 5091
663 5141
664 4969
665 5197
666 5282
667 5037
668 5291
669 5462
670 5137
671 5380
672 5631
673 5229
674 5387
675 5720
676 5413
677 5513
678 5788
679 5578
680 5662
681 5849
682 5686
683 5805
684 5924
685 5756
686 6001
687 6124
688 5806
689 6070
690 6294
691 5918
692 6145
693 6442
694 6049
695 6209
696 6589
697 6262
698 6321
699 6634
700 6430
701 6526
702 6718
703 6510
704 6662
705 6831
706 6648
707 6866
708 7004
709 6702
710 6944
711 7209
712 6820
713 7021
714 7394
715 7011
716 7180
717 7540
718 7145
719 7259
720 7594
721 7355
722 7476
723 7697
724 7506
725 7649
726 7835
727 7615
728 7799
729 8022
730 7710
731 7975
732 8285
733 7800
734 8059
735 8468
736 7995
737 8206
738 8603
739 8189
740 8314
741 8717
742 8458
743 8495
744 8798
745 8625
746 8729
747 8971
748 8700
749 8902
750 9200
751 8838
752 9112
753 9440
754 8912
755 9192
756 9676
757 9158
758 9296
759 9818
760 9451
761 9496
762 9925
763 9656
764 9675
765 10023
766 9870
767 9974
768 10206
769 9949
770 10194
771 10484
772 10049
773 10330
774 10750
775 10215
776 10501
777 11036
778 10463
779 10607
780 11162
781 10760
782 10815
783 11265
784 11005
785 11052
786 11448
787 11245
788 11299
789 11630
790 11339
791 11564
792 11951
793 11444
794 11742
795 12254
796 11675
797 11951
798 12481
799 11889
800 12077
801 12685
802 12237
803 12248
804 12838
805 12585
806 12554
807 13024
808 12746
809 12765
810 13229
811 12940
812 13125
813 13525
814 13058
815 13382
816 13859
817 13240
818 13515
819 14124
820 13557
821 13744
822 14420
823 13913
824 13874
825 14561
826 14277
827 14182
828 14716
829 14480
830 14512
831 15001
832 14697
833 14876
834 15306
835 14808
836 15167
837 15694
838 14996
839 15314
840 16040
841 15426
842 15553
843 16265
844 15763
845 15702
846 16448
847 16151
848 16036
849 16686
850 16447
851 16487
852 16995
853 16542
854 16781
855 17354
856 16778
857 17118
858 17731
859 17044
860 17316
861 18108
862 17463
863 17465
864 18337
865 17898
866 17786
867 18625
868 18259
869 18128
870 18881
871 18578
872 18581
873 19137
874 18712
875 18948
876 19579
877 19039
878 19287
879 19949
880 19322
881 19542
882 20378
883 19702
884 19726
885 20719
886 20234
887 20109
888 20982
889 20579
890 20438
891 21249
892 20947
893 20904
894 21555
895 21209
896 21426
897 22031
898 21409
899 21726
900 22480
901 21772
902 22041
903 22965
904 22220
905 22257
906 23372
907 22763
908 22511
909 23608
910 23251
911 23020
912 23941
913 23597
914 23535
915 24271
916 23897
917 24106
918 24724
919 24112
920 24459
921 25308
922 24557
923 24702
924 25796
925 25078
926 24993
927 26249
928 25592
929 25289
930 26551
931 26202
932 25944
933 26845
934 26506
935 26483
936 27229
937 26859
938 27008
939 27760
940 27248
941 27481
942 28402
943 27593
944 27674
945 28933
946 28206
947 28113
948 29415
949 28750
950 28510
951 29757
952 29319
953 29052
954 30090
955 29807
956 29733
957 30592
958 30176
959 30246
960 31144
961 30597
962 30774
963 31778
964 30964
965 31100
966 32445
967 31620
968 31490
969 32946
970 32255
971 31971
972 33360
973 32837
974 32508
975 33768
976 33512
977 33298
978 34183
979 33813
980 33870
981 34831
982 34269
983 34379
984 35577
985 34824
986 34871
987 36320
988 35355
989 35143
990 36860
991 36184
992 35784
993 37260
994 36869
995 36476
996 37666
997 37467
998 37178
999 38126
1000 37905