1000 1000
9384 887 2778 6916 7794 8336 5387 493 6650 1422 2363 28 8691 60 7764 3927 541 3427 9173 5737 5212 5369 2568 6430 5783 1531 2863 5124 4068 3136 3930 9803 4023 3059 3070 8168 1394 8457 5012 8043 6230 7374 4422 4920 3785 8538 5199 4325 8316 4371 6414 3527 6092 8981 9957 1874 6863 9171 6997 7282 2306 926 7085 6328 337 6506 847 1730 1314 5858 6125 3896 9583 546 8815 3368 5435 365 4044 3751 1088 6809 7277 7179 5789 3585 5404 2652 2755 2400 9933 5061 9677 3369 7740 13 6227 8587 8095 7540 796 571 1435 379 7468 6602 98 2903 3318 493 6653 757 7302 281 4287 9442 3866 9690 8445 6620 8441 4730 8032 8118 8098 5772 4482 676 710 8928 4568 7857 9498 2354 4587 6966 5307 4684 6220 8625 1529 2872 5733 8830 9504 20 8271 3369 9709 6716 6341 8150 7797 724 2619 2246 2847 3452 2922 3556 2380 7489 7765 8229 9842 2351 5194 1501 7035 7765 125 4915 6988 5857 3744 6492 2228 8366 9860 1937 1433 2552 6438 9229 3276 5408 1475 6122 8859 4396 6030 1238 8236 3794 5819 4429 6144 1012 5929 9530 8777 2405 4444 5764 4614 4539 8607 6841 2905 4819 5129 689 7370 7918 9918 6997 3325 7744 9471 2184 8491 5500 9773 6726 5645 5591 7506 8140 2955 9787 7670 8083 8543 8465 198 9508 9356 8805 6349 8612 3623 7829 9300 7344 5747 5569 4341 5423 3312 3811 7606 1802 5662 3731 4879 1306 9321 8737 9445 8627 8523 3466 6709 3417 8283 3259 2925 7638 2063 5625 2601 2037 3453 1900 9380 5551 7469 72 974 7132 3882 4931 8934 5895 8661 164 7200 7982 8900 2997 2960 3774 2814 9669 7191 1096 2927 6467 5085 1341 2091 7685 3377 5543 5937 9108 7446 9757 9180 8419 6888 9413 3349 2173 1660 2010 2337 5211 6343 7588 8207 9302 7714 7373 5322 1256 4820 4600 7722 9905 5940 9812 3941 5668 1706 6229 1128 9151 5985 6659 3921 9225 2423 7270 1397 4082 5631 85 9293 1973 7673 3851 7626 5386 1223 9300 6641 6043 3899 714 2299 6191 525 2591 8210 8582 8820 9337 7733 1156 5995 8005 380 4770 5274 1777 8851 7256 1861 8143 5580 5885 1994 3206 7622 9568 2505 614 1962 2755 1327 4260 8945 8203 3203 3507 6785 2022 2843 869 9529 5190 8873 9909 9959 499 8037 8809 7754 6249 3304 3334 2134 1649 2891 9755 7568 1747 369 9530 4501 8047 3789 9798 6250 6991 3304 3034 5364 2498 254 4893 7687 9126 1153 3997 5976 9189 9158 3730 5437 2461 3415 3922 461 6305 29 8028 8051 6749 7557 8903 4795 7698 8700 1044 1040 2003 429 6404 4501 682 7648 8539 6160 5152 2536 2135 4340 1693 2216 6128 505 5630 50 965 8286 6430 5344 6336 3178 2901 5239 7972 6950 290 5368 7989 2293 5796 744 3145 2830 8391 1683 5341 3542 570 3827 4233 2262 6043 361 9118 8024 6762 82 6310 3191 5426 8997 6368 4678 4235 691 1627 4525 6058 9615 3169 8206 359 6313 7387 5101 4347 2727 4995 4917 6553 5579 3530 8947 2291 2648 6971 9052 9081 9632 8594 858 8628 1313 1887 9215 8356 3513 91 4413 9480 9611 8970 6190 2275 6356 7642 6621 5434 8988 7889 8339 4567 7771 7285 6857 418 607 2261 5850 238 7206 3060 5218 8519 4946 784 6874 8459 874 7638 4290 484 6608 479 2758 9315 4472 5730 1101 3460 3619 9439 8026 1389 3075 1234 8158 3682 3494 359 271 700 3418 1840 5570 8364 2623 8795 3174 9848 6432 7463 6683 9391 4293 5792 5058 5116 1522 6158 8575 1492 1948 2952 9232 5022 538 3741 5055 4031 4099 5326 1082 7517 3517 3003 2232 6140 1797 5405 2339 4581 9219 9022 3971 9863 4813 5380 4978 2686 1537 9905 4177 3484 9208 9760 4858 9745 3500 9912 128 3951 5237 7561 7819 5106 564 50 1245 8712 1806 9935 3292 7376 8956 3615 3590 3769 8994 4919 2806 6883 4823 6983 6718 4031 3094 1575 127 6594 1487 254 544 3075 7815 4714 8180 8378 4763 5776 7089 2920 5711 6733 295 1018 347 236 1138 5692 5154 3944 2574 6329 926 9292 6711 4019 7218 6837 6964 5056 7091 3859 8131 4905 8572 2662 9634 9686 4790 3074 2605 6852 9806 9251 7869 6504 9486 9007 2196 4640 2950 1121 968 227 6764 7678 597 3982 866 7561 9037 7956 7771 3519 9212 6343 2533 5197 2380 7322 8271 4985 4173 4428 4235 2041 7284 73 7399 5831 1064 348 6951 2031 574 3715 6060 7523 4048 6925 5083 9436 1233 9205 2955 444 1899 5487 5641 4279 9160 263 9263 9684 1042 9849 1724 8325 6273 9123 4155 7336 5822 7458 9366 2748 1172 1777 270 5219 8702 1704 4654 9934 908 3960 6729 2807 5798 8721 7085 1309 5335 2699 992 6377 8899 2716 1053 5172 8190 1560 2507 4011 9017 8225 3110 6540 1 3379 8110 5054 5082 9115 1339 5990 9427 8068 5148 5224 6788 2232 6533 2123 1282 3876 4851 180 6591 2255 5351 1132 3814 7858 1495 9182 6082 4604 5721 2434 7983 182 7488 9416 9297 8826 5405 8723 6893 552 298 33 9135 3182 8507 416 7058 9709 596 10000 1963 2298 7484 5777 155 8978 1310 2588 9933 3383 5022 4267 3564 8861 3683 9212 7686 9087 4286 931 5991 4584 7315 1477 4117 5821 1893 7526 5529 8840 7526 7491 1137 1361 9619 7644 338 929 6583 6622 4311 7956 889 4226 6816 4571 3438 854 9 7723 1784 2351 8658 9098 3828 9127 1270 2072 6652 3150 911 529 640 8399 1889 6611 2394 8578 3891 8977 5200 4553 6932 6088 8778 100 658 8567 953 7018 2642 2736 9369 1299 8185 3196 6777 5806 5267 3429 8955 2529 309 9594 7279 2198 2556 9673 775 6446 5001 2326 998 8284 8413 6128 8383 5422
335 4694
335 2440
160 8422
958 4986
762 1355
973 8763
717 1542
851 1853
483 3663
218 400
174 5155
507 9016
365 9852
264 4791
173 2492
538 38
829 8860
281 872
857 6988
342 6591
353 3971
512 7666
518 3070
84 7362
113 1352
507 9301
668 1639
490 9365
155 1033
876 6105
142 3680
539 3413
637 4970
957 6171
761 2845
815 6650
315 4466
887 2327
40 184
536 6970
622 153
791 4394
110 7290
674 9632
736 4265
296 4549
314 1878
199 6834
356 4950
794 5156
157 8469
934 961
287 8824
359 3172
141 5678
182 3246
991 2762
51 324
955 4101
365 1076
625 2043
920 2660
845 6290
239 3470
977 1552
20 5384
344 3134
957 9305
476 5982
12 3667
913 8968
730 193
869 903
3 8132
208 3175
217 9719
378 1184
473 5488
958 4574
126 5063
798 3934
419 2497
154 3142
475 1727
394 6981
949 3486
31 2306
560 4030
161 6899
425 4563
281 7720
903 1642
481 3011
584 2727
141 8790
724 3709
558 939
432 2494
221 711
691 5906
392 9614
271 3639
668 9422
672 7830
744 6181
900 9096
89 3025
387 9155
233 570
711 9970
31 2374
664 8434
280 2588
650 95
352 1500
465 7340
331 1743
516 2087
916 1350
882 187
635 5012
388 4134
288 2723
644 6774
743 1520
245 5355
140 3125
64 6260
354 7419
270 1713
405 8706
800 2734
820 2735
436 4316
854 1088
451 670
803 6488
563 6838
611 8090
961 5206
912 6705
830 2558
817 3404
822 1893
606 1523
580 2444
529 5362
448 3379
46 2701
788 4883
552 4900
387 2590
427 354
795 6949
507 3037
93 7108
665 5418
821 5922
167 8481
355 5995
438 4124
485 2934
313 6318
18 3932
166 6710
609 9157
746 7070
423 2996
296 1172
560 8570
677 4802
572 6653
926 5341
173 1744
90 3092
567 6528
813 8879
197 3051
334 2125
187 4214
371 8500
569 6795
142 5116
640 9343
264 2438
591 3199
203 9940
632 6514
258 5129
572 1805
684 2347
226 8139
541 496
973 6422
635 7227
726 4159
953 357
473 7646
340 3447
884 8112
662 7604
543 5826
340 217
345 9175
331 597
295 6268
758 2014
861 520
293 4651
877 7833
991 280
636 3954
599 9296
742 6108
571 4938
541 4977
802 4585
801 84
610 9493
441 6497
764 2940
305 5736
607 9874
524 165
350 2252
531 2752
705 6340
987 3166
626 8303
592 1080
408 2548
132 8485
920 9562
54 1932
428 529
820 5495
582 7544
769 1124
640 188
439 4644
395 1989
681 1321
487 4099
753 3019
99 6464
11 4696
180 6506
67 6143
426 8099
979 1473
967 2854
749 4798
273 4548
87 517
160 9913
901 9878
198 2554
4 2933
952 2036
499 8108
155 50
907 3862
4 2335
785 5326
798 4429
634 1764
561 116
15 382
898 5186
98 2101
330 2409
314 3350
635 5880
915 4317
776 8586
987 2766
627 7931
617 7893
570 6630
410 9753
516 6367
834 7396
777 4429
614 3848
301 5027
787 1063
764 630
509 5101
417 3398
983 776
541 4545
827 3321
566 6519
500 1795
547 7135
854 6909
304 3063
843 2687
535 8433
811 9808
870 8835
816 3597
697 7985
383 2325
452 4466
362 9717
38 9344
862 4188
982 603
89 5361
621 3880
294 3942
629 2925
709 7136
943 3163
997 3871
467 4164
501 7812
488 2516
333 6235
951 2291
634 8694
881 5340
294 7495
855 5214
445 6383
324 1476
752 8739
874 6952
466 4812
682 9169
684 4814
978 2500
15 4536
770 5465
108 8347
392 3073
412 5741
588 2624
837 7058
440 8794
621 3282
372 115
419 7372
535 597
765 9884
698 3568
68 5801
336 3675
491 7434
133 7458
530 5950
691 5524
148 5293
350 7630
423 2336
969 2141
256 3044
767 340
937 2026
261 1654
221 7053
205 2958
984 1288
722 9541
998 4827
128 7206
729 3879
171 5170
799 7228
564 1521
661 9222
617 7884
224 2268
293 5383
36 5512
564 2554
863 8609
896 1769
661 1199
377 4969
174 1010
888 9504
674 1255
482 4058
930 3824
45 4397
281 1943
210 8013
748 6856
367 4855
760 3135
743 1282
402 1974
172 1639
959 3414
423 1900
756 1485
91 5662
72 8781
604 3924
321 8001
943 2001
13 6953
808 505
359 9760
895 2526
159 9118
91 4637
627 9561
974 615
866 1938
422 3749
410 6621
401 8864
787 1833
834 8005
357 7459
411 6128
632 6369
129 4570
447 8342
459 5375
11 3606
166 4902
868 8990
927 2491
239 733
706 700
563 2001
833 5458
462 2349
808 18
498 6170
539 570
140 9129
471 5019
393 8586
543 1281
534 6755
744 1708
551 4401
486 3022
721 6789
141 5191
648 9635
984 5326
695 462
631 8143
64 4192
321 5521
539 6555
493 7143
423 931
686 35
95 7309
709 9781
803 8645
785 9546
88 6523
158 6926
603 1736
549 4493
987 297
841 1531
52 4050
957 513
655 7590
873 8449
483 2429
89 2558
338 6577
221 7798
695 5140
15 7006
283 4783
870 524
16 5237
885 1418
300 354
755 2725
237 6351
293 7711
159 7243
24 5165
722 4642
570 2112
261 6411
903 2791
148 9956
90 5917
440 2782
18 3959
376 7807
512 9902
979 4675
378 5266
977 8567
162 7670
834 9135
128 4537
1000 6907
317 7698
840 9261
568 7571
487 2987
768 3009
967 6278
436 137
38 8694
720 4947
213 5368
935 7097
118 9541
675 6096
632 3951
209 8803
852 3631
243 526
448 9691
677 1162
170 7935
564 4796
932 1136
181 7352
298 1321
689 5901
997 8862
402 6975
70 4115
417 3429
583 53
683 1626
503 1434
124 9278
791 2950
236 152
947 961
448 7800
503 6230
550 4629
529 3800
14 590
564 9877
991 3767
195 6985
37 4760
385 5777
210 7072
701 1239
540 4685
836 9491
451 7776
927 9782
363 5251
879 3429
580 6265
854 6759
635 8945
712 770
106 6978
737 6258
35 1143
566 4473
711 5596
633 7266
108 6250
377 1468
602 3559
161 2303
83 9964
228 5039
797 2015
959 9434
555 8431
408 3670
928 660
802 3496
968 8314
261 2719
336 30
632 6893
713 9444
354 3008
663 2314
629 4514
552 97
111 4857
642 7700
482 3070
91 7196
855 7890
737 9370
683 6009
727 5705
734 4296
188 1415
858 8365
725 2252
565 211
724 5739
835 3194
402 627
326 7946
367 1395
590 807
48 457
827 2796
804 2785
841 3861
156 3883
649 574
291 5696
947 2506
68 9367
105 8864
409 3791
769 7291
236 9162
556 9094
252 2602
411 9145
292 7652
436 5589
449 3448
682 5276
201 3957
652 5330
835 3843
561 3950
165 6902
44 4665
956 7573
734 7812
257 3543
497 3641
137 5860
511 8259
847 7429
876 298
925 3295
251 4557
886 4126
320 3254
556 4072
325 3881
897 2720
645 4368
531 3204
747 9730
371 1787
646 5595
853 8859
287 7509
806 7699
345 3514
422 9731
208 948
201 659
730 879
759 4108
180 2054
773 6008
211 6176
905 1303
441 2309
903 5627
486 7087
947 8107
805 7124
638 8752
834 9502
449 1411
70 1393
272 1001
109 3151
557 3382
389 8288
463 4329
984 4952
260 6719
346 1424
862 1515
973 3183
658 5808
912 8130
631 7295
58 5745
138 8079
79 7127
629 5761
142 4187
826 8185
866 4883
834 9640
359 849
624 3445
311 5056
590 3486
645 7284
413 1247
894 6556
301 3043
121 9951
429 5790
550 6551
738 57
242 7043
925 5915
555 3459
659 8110
555 8265
320 9282
119 9217
500 4261
507 4764
319 8264
306 400
702 9971
112 8778
329 130
187 13
56 2418
684 4780
590 8980
90 238
854 5248
881 4996
212 4525
785 10000
115 712
327 644
43 8785
108 6633
762 4097
226 7219
232 3442
211 764
895 4287
618 6895
484 2836
83 3059
54 8338
214 5316
315 8618
681 7999
642 2781
565 1007
639 6036
132 3024
243 5753
546 710
825 3826
464 7757
3 6072
907 4081
492 4486
175 6990
657 1545
162 8389
739 3971
103 5842
849 1380
767 1019
43 839
943 251
960 4285
462 8489
597 5136
207 8925
357 3599
436 114
455 2848
745 9963
703 2111
433 7258
452 7441
172 1887
905 6300
490 5290
540 6947
583 2785
273 2851
987 2044
320 3869
819 9193
658 6677
876 8254
216 5464
926 6620
878 9270
710 2710
596 9681
332 8233
523 7501
447 5821
957 5414
265 2030
425 6229
449 6251
795 7745
773 6619
873 3805
268 6648
620 9440
710 3194
255 9849
529 1771
356 6851
351 1860
32 6230
643 5149
178 8989
569 9907
509 3955
699 4370
988 4304
108 2471
470 2212
4 3727
272 1441
289 3065
187 5527
377 817
28 7542
123 3079
227 3060
400 1766
24 5405
359 9968
689 533
188 7409
231 1677
240 9295
373 8052
493 8243
307 2645
523 781
950 2494
387 6899
977 3329
388 6510
627 8203
959 1139
459 2650
182 5669
429 8147
175 721
15 5659
63 6415
657 5740
736 9555
335 2316
161 9258
508 4636
965 7547
56 2484
38 704
843 5034
684 3349
369 9301
447 7217
938 1150
160 3622
388 4304
43 3222
776 1044
711 4778
387 9463
98 871
418 2894
729 2062
118 8825
859 8767
467 960
260 7894
110 187
336 4058
31 3047
703 4496
717 418
814 97
875 493
307 7524
395 5261
507 404
818 3164
340 6235
353 7935
894 8550
443 9819
6 5505
914 7905
303 7693
188 9945
362 1005
102 6257
749 4527
51 2328
940 3055
810 6797
312 8446
681 8627
913 1003
553 6033
204 8158
662 2347
251 8561
253 5928
872 7554
558 8441
49 2585
112 6011
338 4149
555 5514
662 2278
75 3364
343 1325
327 1755
140 1255
765 1879
226 6343
903 5778
705 828
381 1155
947 7576
161 3291
301 6995
143 3624
489 3991
620 4697
413 4150
826 9694
449 2755
361 4152
383 5588
930 6125
903 2960
787 3184
338 3607
535 2168
810 6637
631 4047
670 1110
452 1126
174 3158
659 4071
765 6586
340 5484
987 1565
504 6053
177 8369
328 5433
968 431
38 1467
634 9305
293 1572
618 1795
256 2276
401 9639
148 708
778 5574
160 9158
993 4894
458 7851
903 6979
348 9961
745 2432
862 3027
493 6712
369 6899
822 4478
272 4661
288 6791
781 1880
587 6688
614 8280
437 7364
610 7125
975 8429
760 5067
28 5230
661 3459
485 6772
836 6874
125 7330
159 2204
216 4946
89 783
662 6504
543 869
501 5248
963 8156
632 2937
718 7572
639 2959
188 9477
935 4018
141 2200
73 5771