1000 50000
2 1 3131
3 2 8137
4 3 22896
5 2 26127
6 1 11686
7 5 28339
8 4 17681
9 5 289
10 5 6420
11 9 3456
12 5 9130
13 10 11059
14 2 29188
15 8 24742
16 4 19060
17 6 6215
18 1 27017
19 6 26322
20 1 6780
21 16 1746
22 20 11978
23 10 11621
24 1 6435
25 9 7231
26 9 12163
27 15 5361
28 27 22687
29 14 4459
30 22 10370
31 12 26048
32 14 12408
33 17 12074
34 11 1579
35 5 13390
36 19 17932
37 16 6849
38 13 5364
39 7 5578
40 19 25867
41 5 29290
42 10 490
43 1 9369
44 6 10236
45 28 14803
46 43 11050
47 42 21715
48 44 28855
49 40 5791
50 36 16488
51 44 6340
52 17 12521
53 23 23779
54 18 13164
55 43 21868
56 47 659
57 17 27562
58 39 30864
59 54 9984
60 15 4235
61 29 22898
62 27 5955
63 1 30054
64 15 20217
65 51 28844
66 58 2698
67 23 22717
68 54 987
69 7 31808
70 50 29049
71 69 19923
72 50 8065
73 69 25607
74 52 4030
75 49 15020
76 34 25874
77 19 6480
78 66 7703
79 19 17154
80 58 25349
81 42 21340
82 47 27351
83 63 27840
84 41 15273
85 1 7137
86 12 19045
87 61 5253
88 16 15774
89 9 11146
90 84 22460
91 28 12839
92 49 19546
93 67 5749
94 73 1260
95 24 27950
96 94 6309
97 38 18612
98 48 31640
99 58 341
100 71 10525
101 54 21197
102 63 19830
103 11 29452
104 88 12978
105 101 1594
106 4 29906
107 15 5113
108 91 16683
109 98 25066
110 32 9483
111 22 22386
112 77 12191
113 109 20158
114 18 27412
115 76 30468
116 13 28925
117 104 11276
118 16 7669
119 43 26352
120 16 10373
121 98 11296
122 77 8008
123 10 6824
124 5 4684
125 6 182
126 112 27580
127 47 6486
128 7 15292
129 72 22401
130 1 31637
131 115 25174
132 55 3090
133 25 9895
134 133 29482
135 67 8631
136 57 7390
137 110 18754
138 90 9061
139 125 13502
140 103 25223
141 25 27617
142 1 23111
143 85 32355
144 94 9412
145 48 18693
146 30 865
147 12 3026
148 12 18212
149 64 13733
150 36 6236
151 92 2283
152 107 24967
153 146 32170
154 71 24946
155 1 1219
156 75 10402
157 34 4212
158 66 1523
159 59 1568
160 138 9855
161 155 32083
162 134 27841
163 129 28673
164 51 17147
165 40 16398
166 13 27860
167 95 13843
168 166 7238
169 167 23904
170 163 19895
171 93 24893
172 24 12134
173 164 20342
174 121 6153
175 93 25622
176 5 20661
177 115 17010
178 59 13821
179 83 16233
180 1 29790
181 139 8427
182 45 25563
183 16 30392
184 44 18148
185 163 28778
186 39 28796
187 41 21686
188 172 5531
189 53 32239
190 130 19921
191 176 32715
192 45 1837
193 94 23146
194 156 29021
195 21 24212
196 93 9238
197 76 10051
198 5 1207
199 130 19553
200 180 12073
201 152 13010
202 7 26121
203 158 7605
204 92 19977
205 180 25831
206 63 30867
207 185 29897
208 14 432
209 102 31556
210 79 17705
211 117 26122
212 168 28396
213 15 5662
214 40 27312
215 29 27798
216 95 30428
217 101 5280
218 204 24229
219 178 11971
220 90 8055
221 21 16743
222 136 32151
223 134 4760
224 185 19462
225 146 20231
226 157 27560
227 159 8785
228 226 17829
229 32 9348
230 186 17680
231 29 16608
232 170 5063
233 209 31194
234 180 7834
235 125 11879
236 120 9391
237 232 17526
238 149 22052
239 111 23742
240 151 17911
241 41 29627
242 140 13091
243 51 5107
244 13 27916
245 175 32126
246 16 22301
247 146 26309
248 154 20400
249 142 14986
250 138 32302
251 43 30505
252 242 19575
253 217 4893
254 64 3972
255 184 2757
256 147 9035
257 181 31592
258 6 32226
259 169 28536
260 149 32232
261 128 16403
262 141 30753
263 160 12239
264 150 18528
265 123 8887
266 90 27050
267 193 6033
268 77 22936
269 224 18019
270 246 19197
271 245 2101
272 158 27593
273 253 27671
274 136 16941
275 180 7526
276 139 25856
277 59 32588
278 30 4962
279 48 8582
280 24 28575
281 104 29290
282 92 24918
283 101 21032
284 193 25306
285 181 27472
286 237 15832
287 283 29844
288 166 31546
289 201 16336
290 95 2636
291 13 14919
292 62 25373
293 56 16943
294 156 10281
295 40 30065
296 176 2868
297 45 23978
298 182 31097
299 94 7541
300 187 21252
301 73 748
302 251 12637
303 52 9068
304 1 358
305 113 25753
306 209 29830
307 292 5794
308 261 3335
309 272 967
310 62 18877
311 283 6424
312 66 13545
313 186 3199
314 6 23132
315 296 9216
316 93 26848
317 202 576
318 43 723
319 202 7236
320 305 533
321 77 15484
322 41 13093
323 98 14080
324 12 19334
325 1 13081
326 310 8040
327 278 11779
328 7 23172
329 247 6897
330 98 16456
331 220 17490
332 85 14132
333 89 21075
334 52 9092
335 127 6821
336 240 21775
337 325 7552
338 323 3183
339 291 21480
340 156 23394
341 272 13103
342 66 25712
343 319 2491
344 265 15822
345 52 6409
346 193 31619
347 44 4338
348 305 9417
349 327 20525
350 157 6326
351 67 3606
352 75 9755
353 161 20909
354 4 23213
355 201 23010
356 25 19810
357 310 23312
358 300 26654
359 190 13767
360 72 29839
361 81 2766
362 160 28757
363 16 20584
364 89 27751
365 250 19671
366 287 31666
367 144 6687
368 247 29955
369 154 5900
370 113 3110
371 140 26998
372 195 1616
373 313 30148
374 292 3514
375 139 28591
376 251 26767
377 159 26697
378 139 5896
379 123 32061
380 16 7381
381 224 3416
382 272 31168
383 18 5704
384 131 5517
385 166 8100
386 165 8996
387 384 22317
388 387 16114
389 131 16980
390 132 19596
391 236 10492
392 271 22421
393 380 7552
394 325 31715
395 318 17912
396 29 6365
397 11 19128
398 108 21543
399 109 3610
400 137 12162
401 222 4478
402 373 13805
403 129 11150
404 120 1040
405 218 29639
406 334 12251
407 192 1845
408 219 21355
409 130 2685
410 124 16173
411 391 3361
412 332 5957
413 385 12800
414 324 24625
415 47 16668
416 274 16041
417 59 1696
418 30 28362
419 394 8994
420 63 13940
421 264 12581
422 156 22257
423 224 25570
424 74 16855
425 135 840
426 252 5423
427 357 26945
428 414 8918
429 117 25655
430 46 1828
431 312 8919
432 2 4812
433 3 3348
434 111 3075
435 117 11887
436 299 2789
437 56 5494
438 22 29972
439 298 19595
440 268 23714
441 101 20455
442 370 17969
443 214 9439
444 438 6744
445 23 30309
446 47 17993
447 133 23249
448 372 20401
449 256 9954
450 274 24544
451 447 29183
452 2 2602
453 426 12227
454 371 20877
455 235 697
456 373 12692
457 26 11364
458 155 11898
459 368 16003
460 293 12435
461 206 29074
462 250 12008
463 72 17556
464 418 27937
465 392 18960
466 391 20649
467 111 18010
468 386 4364
469 430 787
470 186 18340
471 111 31731
472 422 8820
473 192 18630
474 445 15956
475 243 26805
476 291 27727
477 192 21191
478 473 26185
479 49 28584
480 236 14052
481 373 24744
482 451 22693
483 181 14342
484 118 20563
485 172 1647
486 394 18080
487 126 25026
488 134 25868
489 126 18710
490 97 31237
491 379 2558
492 231 10323
493 316 2828
494 246 9651
495 208 8083
496 78 19650
497 238 18609
498 252 1565
499 363 1933
500 243 19655
501 168 9438
502 218 20939
503 312 4525
504 290 802
505 299 17755
506 281 31190
507 300 15589
508 89 4968
509 114 32615
510 346 14960
511 65 19423
512 508 8835
513 411 21556
514 316 31577
515 256 10615
516 388 24367
517 46 15720
518 43 107
519 229 7484
520 460 23167
521 505 18845
522 80 27151
523 350 20467
524 376 12374
525 119 2274
526 18 1478
527 403 8211
528 55 32750
529 276 18744
530 380 28321
531 57 17994
532 185 13397
533 102 8981
534 159 32201
535 60 18935
536 391 7403
537 519 21989
538 29 2808
539 161 17838
540 317 21989
541 25 29828
542 23 31998
543 325 31672
544 285 205
545 305 25029
546 20 10813
547 438 14992
548 222 19711
549 532 7406
550 341 2349
551 79 4455
552 124 20525
553 437 24122
554 390 12505
555 83 21664
556 182 11996
557 57 853
558 379 10591
559 323 29269
560 524 5350
561 362 19427
562 409 3188
563 144 5840
564 472 32246
565 224 26106
566 161 30174
567 389 8467
568 168 19983
569 19 19108
570 294 17401
571 259 26449
572 398 14853
573 267 27230
574 150 10291
575 340 19314
576 363 1
577 375 10651
578 320 1936
579 305 8083
580 444 28674
581 255 11586
582 561 11046
583 227 23171
584 301 17495
585 369 30507
586 176 16545
587 563 7240
588 434 18982
589 168 21158
590 25 10944
591 498 664
592 357 23016
593 336 4340
594 276 8663
595 459 19808
596 184 8170
597 487 5580
598 231 9291
599 387 21312
600 263 13518
601 343 13272
602 243 14105
603 331 17933
604 311 1544
605 506 22837
606 227 30288
607 569 18253
608 215 3682
609 13 3063
610 105 30098
611 190 19647
612 156 24184
613 106 13986
614 580 28822
615 443 21713
616 70 30012
617 62 17586
618 31 19369
619 271 27432
620 270 26739
621 475 3860
622 50 25641
623 327 32028
624 109 23862
625 614 6315
626 30 12552
627 474 32312
628 588 20594
629 386 6860
630 608 13135
631 581 23742
632 35 12137
633 28 25025
634 92 13977
635 381 17954
636 328 16431
637 189 31050
638 226 24979
639 354 15242
640 267 23085
641 20 10520
642 429 5763
643 327 30292
644 464 28321
645 57 16720
646 374 9150
647 245 7312
648 71 24860
649 498 14094
650 84 17456
651 408 17793
652 217 12291
653 58 4319
654 103 28632
655 384 20001
656 540 27919
657 29 9030
658 464 31817
659 35 32154
660 132 1485
661 117 7480
662 469 3371
663 640 31182
664 338 23583
665 49 25760
666 609 21687
667 477 3024
668 537 11960
669 336 17116
670 221 9279
671 428 13416
672 436 20900
673 490 24894
674 605 19619
675 39 4243
676 133 14014
677 292 5516
678 146 20189
679 609 3584
680 427 17976
681 591 32384
682 596 23670
683 374 28564
684 652 1814
685 229 28744
686 390 10255
687 614 8679
688 242 6067
689 4 12551
690 269 1497
691 581 24517
692 140 30267
693 409 1362
694 55 23581
695 510 9903
696 254 6448
697 454 3252
698 368 25525
699 288 31575
700 221 22501
701 124 28203
702 468 14481
703 77 32295
704 253 8966
705 625 21673
706 177 14899
707 344 20410
708 630 3342
709 496 15252
710 322 15411
711 40 17762
712 486 8910
713 484 2886
714 292 1724
715 113 28064
716 464 5101
717 497 1422
718 583 9997
719 558 25775
720 295 11107
721 283 557
722 31 4089
723 369 30970
724 136 6141
725 257 31577
726 86 2663
727 129 8097
728 516 1244
729 539 27197
730 546 30162
731 649 14584
732 671 502
733 68 29560
734 590 22730
735 709 9479
736 60 15507
737 137 25498
738 313 16754
739 702 10251
740 720 2001
741 228 31658
742 579 30208
743 357 7924
744 42 13600
745 234 3490
746 526 30017
747 482 998
748 129 15559
749 281 26865
750 494 18194
751 34 17080
752 267 13918
753 515 5880
754 235 7399
755 363 23927
756 30 8529
757 641 26510
758 507 16968
759 426 24804
760 420 32100
761 360 19836
762 421 23887
763 484 10482
764 134 13097
765 636 2817
766 361 32555
767 724 30025
768 729 19595
769 144 11855
770 278 1184
771 692 19910
772 677 32071
773 484 24077
774 431 18053
775 146 14072
776 137 31598
777 103 30163
778 177 6725
779 439 13988
780 398 10212
781 369 29361
782 272 8798
783 328 10306
784 680 1764
785 10 12200
786 90 28389
787 475 24958
788 246 2169
789 257 29231
790 448 28160
791 586 9913
792 404 8454
793 734 18096
794 540 11371
795 219 28549
796 194 12736
797 376 11528
798 123 26099
799 556 31532
800 122 16687
801 296 5386
802 576 26110
803 655 13609
804 793 945
805 500 11005
806 756 14337
807 390 27053
808 188 13302
809 189 29722
810 67 10248
811 513 18972
812 589 15237
813 165 15118
814 709 4914
815 77 16782
816 298 11061
817 98 19582
818 416 2098
819 174 6478
820 369 949
821 609 894
822 500 14288
823 269 27998
824 354 19973
825 652 9753
826 391 13669
827 75 28913
828 715 1018
829 485 4556
830 790 1891
831 153 752
832 728 18622
833 368 14347
834 128 1995
835 824 4726
836 584 29005
837 437 27322
838 475 5300
839 332 21332
840 243 23802
841 451 30901
842 627 4299
843 658 17037
844 522 7656
845 242 6729
846 815 13261
847 812 31450
848 78 29074
849 554 11705
850 464 11023
851 277 22824
852 776 2371
853 114 17338
854 350 2551
855 49 28949
856 409 8862
857 323 31735
858 16 2688
859 129 20855
860 73 28695
861 426 12686
862 649 7609
863 482 6357
864 768 20856
865 425 30608
866 51 19527
867 843 23020
868 209 23646
869 502 25989
870 136 26335
871 472 20523
872 163 13497
873 578 13286
874 684 1740
875 867 25655
876 795 13647
877 375 10401
878 17 24175
879 487 104
880 236 26681
881 627 21401
882 100 22970
883 340 13642
884 462 20325
885 559 6947
886 607 3765
887 341 11806
888 478 32019
889 113 6282
890 27 32249
891 691 30038
892 755 31832
893 259 17548
894 728 9015
895 703 2332
896 52 2461
897 785 29659
898 666 21938
899 824 16331
900 42 6945
901 83 9117
902 327 30912
903 722 31860
904 381 14707
905 248 5612
906 708 31822
907 839 13147
908 14 10233
909 156 15959
910 498 11609
911 896 15992
912 439 23916
913 364 32350
914 767 22133
915 327 502
916 828 19546
917 232 12794
918 137 12362
919 844 24759
920 305 31650
921 680 3091
922 733 8722
923 430 206
924 249 28412
925 680 17160
926 480 21020
927 210 24580
928 254 24430
929 650 3371
930 606 1612
931 617 14420
932 693 17367
933 788 27970
934 371 21657
935 214 13422
936 266 10601
937 415 20231
938 139 9102
939 429 29752
940 366 23591
941 578 29609
942 520 31434
943 554 24904
944 426 24427
945 21 11849
946 650 9087
947 249 21355
948 396 13922
949 434 28798
950 483 6390
951 290 1314
952 787 31886
953 767 9937
954 410 18698
955 442 22560
956 265 20035
957 197 25921
958 147 9385
959 126 27085
960 607 298
961 883 25536
962 665 86
963 619 30662
964 758 11457
965 786 19125
966 104 17577
967 369 5210
968 943 729
969 846 20344
970 136 28365
971 694 11022
972 275 30743
973 403 8409
974 957 24834
975 593 21786
976 802 15476
977 318 9113
978 238 793
979 858 32234
980 624 957
981 872 32495
982 799 13050
983 77 22430
984 848 7700
985 270 30980
986 556 1313
987 247 8074
988 901 24685
989 211 9080
990 120 21788
991 144 12983
992 415 23825
993 620 22491
994 243 9743
995 467 29281
996 601 27678
997 603 1076
998 610 21297
999 626 30838
1000 724 1029