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