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