/home/toolbox/public_html/solutions/104/10487/x.in
1 1000
2 758141
3 777284
4 368808
5 772863
6 362890
7 181224
8 463046
9 953556
10 312428
11 307074
12 731442
13 654267
14 558549
15 124022
16 61028
17 951627
18 404503
19 57532
20 152654
21 126432
22 1388
23 522192
24 306880
25 153383
26 101245
27 257016
28 60118
29 627424
30 120539
31 900209
32 989840
33 233703
34 312257
35 967713
36 643311
37 771218
38 726759
39 9581
40 596358
41 365014
42 107575
43 170740
44 953414
45 217984
46 500954
47 761770
48 89415
49 929447
50 122195
51 637276
52 232636
53 227870
54 924194
55 103889
56 945816
57 462454
58 579313
59 645110
60 72289
61 303385
62 541625
63 28080
64 620890
65 893887
66 226013
67 296413
68 912086
69 504012
70 426788
71 447210
72 270028
73 38687
74 517186
75 386733
76 972536
77 787900
78 835143
79 890260
80 913145
81 530657
82 928541
83 889611
84 507554
85 631636
86 512542
87 623312
88 541677
89 11530
90 602363
91 739122
92 512618
93 368473
94 883149
95 718029
96 895660
97 969829
98 820518
99 467103
100 673611
101 203406
102 215128
103 782869
104 876113
105 557239
106 495916
107 222693
108 147905
109 228256
110 176883
111 54477
112 558890
113 665843
114 640351
115 482489
116 435655
117 66121
118 245817
119 24224
120 678058
121 341510
122 313588
123 994462
124 166203
125 112231
126 186185
127 777434
128 263356
129 794579
130 104583
131 32272
132 343832
133 556022
134 531627
135 82623
136 725670
137 354407
138 379493
139 858421
140 455153
141 787057
142 296637
143 482797
144 432554
145 631052
146 918431
147 387630
148 320651
149 105949
150 450172
151 100685
152 90246
153 77129
154 471948
155 254697
156 966371
157 509597
158 641194
159 97205
160 321884
161 627719
162 930784
163 694641
164 882531
165 99718
166 129204
167 862232
168 979754
169 14853
170 581645
171 562555
172 487376
173 328082
174 38480
175 259363
176 556578
177 106100
178 277895
179 503522
180 615791
181 480743
182 838990
183 561690
184 666529
185 459587
186 687172
187 506930
188 165290
189 850113
190 288252
191 944488
192 290379
193 569531
194 774462
195 776160
196 936190
197 217116
198 909781
199 494225
200 718884
201 735778
202 209795
203 516896
204 218439
205 635035
206 405176
207 844857
208 806632
209 620339
210 685549
211 111348
212 861089
213 533130
214 275886
215 434302
216 607730
217 416779
218 23682
219 362499
220 695287
221 572021
222 854820
223 979961
224 461584
225 343597
226 491428
227 979550
228 4287
229 445145
230 394974
231 958665
232 102885
233 871846
234 445905
235 753084
236 242204
237 37457
238 781191
239 321422
240 205157
241 618513
242 885507
243 799366
244 278258
245 991963
246 937317
247 892816
248 568603
249 956906
250 319439
251 275507
252 341460
253 732328
254 846435
255 704770
256 821637
257 584967
258 550561
259 857300
260 962072
261 702358
262 256165
263 626542
264 672813
265 87025
266 625933
267 687687
268 533768
269 316823
270 396599
271 150970
272 159289
273 632510
274 78807
275 850527
276 171010
277 434170
278 686364
279 266226
280 749507
281 702170
282 103172
283 622521
284 734976
285 539505
286 989633
287 776361
288 433977
289 482759
290 810901
291 114128
292 79255
293 759448
294 14739
295 248924
296 128189
297 730748
298 933842
299 352809
300 686531
301 337909
302 635628
303 415414
304 925236
305 342074
306 541563
307 392319
308 229360
309 816609
310 237713
311 960827
312 40194
313 661767
314 750839
315 92950
316 198626
317 281098
318 558415
319 234576
320 514507
321 441719
322 511025
323 68756
324 230318
325 765507
326 571616
327 425568
328 244067
329 6445
330 938356
331 931786
332 675821
333 119184
334 731585
335 577664
336 912134
337 40325
338 942349
339 934694
340 522790
341 23367
342 682982
343 537683
344 404720
345 763364
346 560329
347 828595
348 129812
349 396114
350 509779
351 198630
352 895900
353 415965
354 508275
355 425366
356 146043
357 27389
358 450180
359 140307
360 715504
361 727316
362 359135
363 688490
364 860502
365 984196
366 300700
367 718865
368 607959
369 641311
370 326976
371 609140
372 972547
373 243372
374 969553
375 941785
376 966909
377 479928
378 368675
379 518559
380 544397
381 478488
382 655262
383 707898
384 25365
385 276010
386 504996
387 735983
388 474144
389 158789
390 552814
391 296366
392 320557
393 862796
394 764902
395 40490
396 449671
397 490414
398 341279
399 70929
400 186847
401 439848
402 360783
403 924841
404 419343
405 820480
406 192116
407 962432
408 230280
409 739122
410 474299
411 308409
412 379477
413 430533
414 648167
415 653061
416 502037
417 509975
418 893228
419 704792
420 710331
421 232028
422 400440
423 342807
424 751281
425 996546
426 106854
427 785887
428 35494
429 729079
430 238553
431 943535
432 673471
433 884216
434 90351
435 11821
436 549195
437 718082
438 830517
439 779916
440 543892
441 780148
442 484162
443 882555
444 649916
445 76722
446 64961
447 71264
448 8123
449 222370
450 148083
451 652048
452 502622
453 630499
454 894673
455 184159
456 557195
457 561303
458 183718
459 342021
460 592532
461 949735
462 990057
463 803829
464 941268
465 736534
466 947254
467 612264
468 436044
469 812268
470 213910
471 182768
472 878565
473 762669
474 692689
475 851796
476 525577
477 855830
478 98177
479 851650
480 908994
481 133549
482 353137
483 513934
484 579727
485 892824
486 326665
487 36950
488 661356
489 139499
490 716683
491 971529
492 714417
493 553854
494 447793
495 498186
496 246682
497 442085
498 444836
499 390889
500 231677
501 529965
502 286212
503 881515
504 890054
505 927189
506 711142
507 207236
508 22094
509 827096
510 786585
511 499434
512 120389
513 881558
514 751198
515 377939
516 820432
517 170396
518 598032
519 34708
520 610820
521 930799
522 275712
523 628444
524 145246
525 251445
526 610296
527 721822
528 530078
529 530450
530 248440
531 323954
532 542038
533 980029
534 677275
535 672684
536 777182
537 435835
538 296946
539 21746
540 843025
541 427761
542 324950
543 205689
544 6449
545 421214
546 430146
547 180016
548 490679
549 227839
550 461462
551 393498
552 333643
553 522401
554 809763
555 574638
556 706418
557 443514
558 92101
559 324346
560 515200
561 680677
562 937108
563 307642
564 58140
565 894315
566 333017
567 961341
568 660773
569 293808
570 364525
571 53127
572 466541
573 714602
574 519044
575 703400
576 16076
577 390334
578 396021
579 473186
580 467950
581 757009
582 589339
583 20310
584 138114
585 111506
586 656263
587 459983
588 146723
589 378301
590 661442
591 768436
592 607187
593 189585
594 644950
595 852673
596 314466
597 613450
598 580589
599 78476
600 277347
601 126845
602 134144
603 143252
604 599966
605 128090
606 560864
607 654174
608 215246
609 741732
610 738399
611 726869
612 18491
613 524299
614 270510
615 360209
616 188520
617 282547
618 231472
619 619280
620 285101
621 917584
622 935086
623 368005
624 599940
625 967986
626 183776
627 88303
628 533495
629 332359
630 134376
631 195388
632 513191
633 476073
634 289225
635 515456
636 488935
637 492000
638 491715
639 326458
640 586327
641 348226
642 697624
643 263783
644 483552
645 912099
646 869666
647 318955
648 26452
649 467721
650 870049
651 164934
652 868109
653 81066
654 147568
655 584733
656 597668
657 81467
658 218928
659 757484
660 22707
661 161130
662 854762
663 107369
664 569132
665 736691
666 52961
667 10842
668 838007
669 477343
670 501597
671 377397
672 426062
673 695630
674 129272
675 251183
676 898610
677 228267
678 447420
679 112613
680 348663
681 19696
682 292953
683 664980
684 719380
685 729291
686 909658
687 37460
688 159275
689 440308
690 30216
691 527399
692 698119
693 59157
694 455365
695 757182
696 102686
697 379206
698 567848
699 617517
700 895117
701 909586
702 401511
703 77368
704 717053
705 889994
706 736687
707 777022
708 372918
709 621425
710 136692
711 874941
712 930978
713 137669
714 300912
715 534521
716 814547
717 113268
718 992354
719 651169
720 157201
721 110090
722 281519
723 369075
724 171672
725 140295
726 496636
727 936890
728 310449
729 101206
730 364310
731 949045
732 829827
733 460510
734 379991
735 316586
736 293506
737 418900
738 911678
739 544021
740 172183
741 630198
742 225101
743 591469
744 469683
745 637074
746 613349
747 38966
748 283400
749 94467
750 244194
751 275470
752 847118
753 232865
754 789108
755 182461
756 592385
757 362936
758 226428
759 592252
760 314937
761 372198
762 583540
763 691300
764 424536
765 952352
766 479806
767 132890
768 600863
769 154398
770 360587
771 337666
772 175656
773 635747
774 618795
775 863259
776 509603
777 719644
778 28994
779 129809
780 563875
781 689665
782 432177
783 373043
784 404699
785 106982
786 217097
787 477277
788 800738
789 304472
790 203890
791 512566
792 620441
793 353613
794 452264
795 985620
796 845804
797 59891
798 891723
799 649265
800 474258
801 47070
802 936758
803 398143
804 878582
805 943158
806 69929
807 210304
808 976490
809 736742
810 268806
811 301995
812 16303
813 532334
814 403838
815 25798
816 87078
817 180721
818 78828
819 614246
820 718976
821 691990
822 677407
823 875359
824 577784
825 53883
826 112212
827 292337
828 881030
829 373595
830 192745
831 669552
832 357901
833 969966
834 881001
835 277706
836 162678
837 706824
838 247654
839 230668
840 185400
841 352639
842 133976
843 508788
844 848545
845 100250
846 927179
847 696112
848 534232
849 210436
850 570343
851 642316
852 185046
853 637652
854 207900
855 240927
856 924022
857 630671
858 861038
859 448094
860 927312
861 795474
862 268173
863 317966
864 854927
865 179900
866 50123
867 141309
868 290419
869 692137
870 672586
871 677111
872 523927
873 684464
874 341699
875 14597
876 422234
877 27653
878 851735
879 465433
880 1833
881 414870
882 974752
883 152746
884 119731
885 334081
886 273984
887 785029
888 777907
889 327946
890 306471
891 215153
892 770280
893 153306
894 232241
895 632114
896 412543
897 244457
898 915004
899 847438
900 374592
901 50954
902 19109
903 148930
904 309354
905 399951
906 694468
907 233987
908 710930
909 560319
910 177505
911 795905
912 664017
913 553911
914 955865
915 656255
916 592511
917 891133
918 204810
919 65964
920 876031
921 533910
922 207472
923 894460
924 578032
925 652791
926 972482
927 268909
928 861422
929 186686
930 100685
931 334046
932 679138
933 89665
934 38143
935 168419
936 233206
937 849997
938 680939
939 199066
940 307802
941 330720
942 285028
943 769440
944 11992
945 306839
946 562024
947 818027
948 64098
949 505199
950 711531
951 262257
952 570681
953 27223
954 708231
955 18509
956 134663
957 814476
958 66668
959 962568
960 650469
961 342634
962 310275
963 916853
964 315077
965 955128
966 633072
967 565340
968 841768
969 234570
970 330610
971 95167
972 422176
973 587864
974 178300
975 617413
976 452430
977 738470
978 222807
979 613550
980 833972
981 51906
982 658532
983 932436
984 366147
985 429856
986 569477
987 886246
988 604805
989 615599
990 702796
991 140698
992 381123
993 201652
994 399354
995 534579
996 316119
997 421733
998 92048
999 860986
1000 527169
1001 368103
1002 1
1003 594149
1004 0
1005