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