===INPUT===
1000
4739 1153 2533 5038 1207 7007 833 9182 7309 128 3350 1348 7724 1022 6859 2730 9625 6587 1799 2222 568 4154 3185 7992 8770 4978 2983 397 3545 7422 2051 2179 2200 2729 155 2727 3502 4665 2808 1435 7836 6120 41 8036 5244 5483 9065 4915 8261 8156 5662 7602 7773 6523 3780 5057 6238 7093 8777 2273 9084 6003 2906 1554 1557 1431 1966 7304 7834 1490 6529 9187 286 6009 9268 8735 1868 8153 3475 7848 8734 1352 9847 6418 2539 3663 4477 4105 4736 3493 3430 293 1427 1869 1136 7712 4276 435 9398 4362 5620 2498 52 3068 9882 8474 1038 3932 1556 6416 9968 1153 6523 9623 7736 9480 2331 750 9636 4710 5425 5049 822 2079 4197 1716 6543 2838 5386 3461 9483 3765 3764 8562 6809 1599 2025 1043 2030 8389 3755 6281 9338 7878 7285 4191 11 1866 1796 8192 65 7105 2408 410 2130 1223 971 1937 6446 9772 5634 310 2085 8577 8497 3017 520 1188 3987 1789 8990 2832 1706 1755 1592 7887 1316 5130 2951 2930 7679 2254 4092 5570 7198 9838 4128 5591 9117 5851 9077 8169 7633 253 5437 598 1540 6127 3049 2291 8751 9327 5957 9494 9672 5471 8722 6163 3551 287 3972 2454 9444 4431 8189 5041 7643 303 9193 4550 2562 8170 4652 3878 1410 2482 2297 8667 100 7853 3781 1556 102 5585 875 9343 2942 2524 9168 8348 9103 823 2250 30 346 379 3581 8341 7302 5925 9766 7899 5187 8838 9835 6796 8859 2894 9330 7593 6250 2314 5778 2446 303 5803 3448 9315 5060 2170 586 6896 2187 8441 5329 8452 201 2683 7938 7880 1608 3062 3885 5247 2967 1960 507 4705 4820 6232 4961 8152 2013 7791 8554 9082 3491 2998 4516 3385 6129 593 7081 7688 9964 925 6353 9247 8778 854 8150 1184 632 6924 2424 2170 7367 5799 4530 6045 3238 3320 8749 5392 3206 7794 3603 5168 8442 9033 519 8730 1741 3674 1971 651 8697 1067 8530 5446 5173 4100 319 902 4622 495 9085 212 874 1083 3449 6074 1001 7223 5853 3097 6669 4461 1639 2296 1339 3549 2425 9566 1281 1452 7793 1907 363 6044 668 4354 9505 8558 1463 7569 5700 69 406 5188 7001 9933 8024 5167 1332 2620 5963 3786 3033 5160 9820 4410 238 6729 2338 541 5157 6431 9068 1622 505 2503 4407 9243 7383 1755 1652 1307 3392 5256 8522 1651 283 9700 8232 7123 3168 1967 9902 1485 8418 8649 1756 6109 8909 4837 2426 575 2032 9740 8458 6157 380 5941 6987 6584 8207 9219 3568 122 4634 6207 1168 2890 1817 6360 3263 7023 7316 1033 1325 8952 2737 618 5806 6043 4685 7449 458 2860 1595 506 8917 3152 3116 5164 177 5427 2400 9567 178 9911 8235 6387 610 3695 9883 8354 8759 8907 9225 6129 1186 7684 6926 9218 8473 6282 616 1918 1496 1019 94 3713 4307 6439 6480 3991 2415 5250 1410 2182 8130 618 3179 2571 247 7594 392 8281 2342 8094 1750 6879 8804 7912 5713 3994 6551 1251 1622 6139 4509 5717 2032 9578 478 9434 1185 7851 6670 7038 478 5072 520 8379 3089 9311 9079 4085 6441 1205 2550 3330 2388 6219 9099 4142 9312 4185 7743 493 31 9624 226 6354 4633 2476 9724 7904 1510 4418 1511 511 7564 8709 5195 6146 6229 7239 634 9702 453 815 8206 8477 8811 4862 4287 4076 1734 1495 8969 5906 42 6894 6045 5530 9986 6479 791 8274 216 5747 8337 2429 9955 4958 8150 7526 1041 300 6808 4183 341 3262 6278 4216 7794 5135 4952 2459 8009 716 6365 4504 6031 3012 8360 2885 131 7052 9942 6552 9166 3366 4147 9984 3196 8146 5662 5712 2298 213 5098 1534 577 4394 8486 4651 6290 8839 1742 3 1425 177 8051 1192 7015 9122 7466 6794 899 2122 8817 9402 7633 7651 6007 1871 1086 6762 4924 4552 3259 4779 3062 1731 3888 1452 7461 3470 8658 2157 3674 3388 1832 6829 3060 3226 9418 9681 3722 1602 7451 9313 6576 7536 2297 2291 9348 3827 3986 8989 2344 4710 3514 2341 3861 6256 4026 4138 3357 2249 1131 3513 7058 6334 4563 1785 7942 2982 4303 9688 322 5925 2130 2105 8827 625 1709 1518 6898 9252 7744 4403 3546 7506 2831 4555 719 8091 232 6319 7237 2147 116 179 3807 5760 1517 1387 7394 5188 4607 1919 3289 1579 3841 4747 7626 9623 4598 106 9752 1354 9231 580 6139 6611 5619 853 5229 6190 3842 8784 4918 2213 3894 9972 1434 91 4539 6141 6401 5227 8977 7998 4247 188 816 7342 7013 6136 1563 6145 9072 2077 1879 953 1409 819 3694 2284 6277 1007 8911 9255 8662 2151 8153 1251 281 4791 344 7943 5321 5300 2398 94 7652 1039 5702 7995 7476 2429 6149 8266 4385 3796 1841 1417 9861 4040 3511 9367 1121 1735 3288 2379 1646 2945 5988 2920 3526 220 1130 3919 4803 8263 29 8150 792 462 8779 664 5952 2045 1003 3950 2515 8696 4597 7564 1216 5307 8935 4238 2615 9069 3076 8036 102 1771 5135 2732 4407 2082 1817 5359 9176 9324 1672 959 6555 3519 280 4544 1359 4722 6182 2915 5887 4930 3882 3611 7177 6004 5701 9578 8145 5211 8172 9195 5639 5388 740 6214 7302 3744 2190 479 6447 8811 7300 5087 5126 6779 1461 2984 6298 9778 1917 6499 2523 2151 8921 1773 7591 5402 9722 5841 6230 5559 9496 6823 1847 8445 9816 9438 1114 5616 1985 4421 9375 2171 8763 417 7823 2778 5673 9034 890 1654 4777 1046 512 3218 5498 5658 2596 5126 1549 5102 5454 9786 6223 6048 7071 5174 9558 1788 3115 4072 265 9259 7170 7205 9781 7370 6031 5555 685 9901 3397 9910 9810 6211 9078 794 420 3034 6007 1921 9143 8902 2768 6300 4089 6159 568 7695 1795 8729 3409 6993 8815 6761 1023 2369
1000
451 784
118 197
720 896
68 225
497 630
437 973
518 901
87 416
170 335
12 885
551 906
15 576
1 499
466 993
84 977
166 269
311 709
140 286
326 891
633 903
336 418
245 894
115 885
61 317
75 134
572 958
203 624
16 727
421 824
428 522
354 392
62 534
72 967
505 768
581 708
279 820
590 798
892 919
90 839
394 961
188 633
130 594
122 350
329 776
15 821
711 919
104 931
121 799
666 884
620 774
325 367
59 627
537 540
241 343
245 578
338 997
403 784
199 449
22 966
296 866
504 875
291 466
340 718
547 782
485 507
490 796
22 209
523 974
120 556
54 829
508 814
538 719
721 851
492 547
431 731
704 963
71 624
585 872
270 623
485 824
184 572
564 822
345 554
759 845
532 606
875 898
63 419
487 902
260 539
462 969
51 374
636 840
354 906
30 933
589 752
414 735
603 888
428 974
411 533
304 879
301 763
620 728
90 220
2 339
50 220
425 808
649 654
653 895
539 955
206 797
18 601
40 737
359 366
76 295
43 219
102 107
339 362
378 430
443 557
270 786
525 650
184 932
630 971
415 462
875 974
244 469
129 300
386 535
612 863
703 735
203 730
345 883
28 828
437 718
244 987
361 919
316 807
235 696
513 696
495 830
328 553
80 948
204 456
406 471
368 874
108 902
90 738
255 863
682 768
356 903
668 733
191 669
552 891
68 646
295 381
157 632
348 828
1 685
57 630
95 645
0 645
173 500
251 449
383 713
110 317
433 593
256 538
239 508
904 973
609 611
120 374
604 969
72 663
503 790
372 396
149 867
552 770
336 401
326 464
299 646
764 847
698 764
612 867
672 719
302 892
24 438
662 916
658 818
613 663
73 418
293 889
575 664
688 715
109 814
398 586
148 176
617 696
688 992
86 323
645 769
277 997
619 641
432 967
172 465
194 510
72 485
477 915
98 880
45 777
791 960
71 660
144 237
606 728
382 907
261 762
368 801
202 587
529 538
803 969
5 287
659 984
194 613
358 921
552 658
505 875
122 651
142 913
24 886
542 581
131 172
100 616
666 751
239 283
186 722
499 807
279 509
111 558
71 583
304 675
119 589
772 986
364 585
158 382
67 437
232 383
103 435
69 991
51 665
298 521
229 841
83 871
632 867
365 945
845 934
126 454
104 947
321 497
516 987
10 871
13 76
28 901
540 841
470 883
78 116
922 980
452 799
526 700
922 984
492 553
284 754
235 815
755 931
72 609
11 519
70 266
602 865
58 848
559 757
249 594
41 44
41 908
324 854
418 865
70 219
204 336
123 195
397 752
144 717
195 919
114 814
554 950
499 665
271 531
120 746
146 585
146 737
275 347
267 415
462 543
45 987
173 772
241 299
104 180
638 753
48 327
240 687
227 781
216 437
163 734
563 625
410 525
312 486
34 968
345 819
473 983
184 903
192 406
325 708
385 968
199 535
776 894
660 668
98 560
421 712
195 387
552 926
269 523
40 420
84 573
239 586
61 126
977 997
392 393
244 911
300 367
111 961
162 999
244 560
745 933
59 216
343 918
396 729
1 910
414 924
650 853
463 705
114 203
793 954
633 737
21 772
181 585
327 862
542 747
124 187
193 270
12 330
78 92
561 615
214 311
87 432
54 249
4 849
111 965
325 351
420 757
369 810
206 234
112 710
180 947
45 413
99 132
48 753
65 804
543 897
652 827
103 984
598 834
360 988
559 683
448 803
283 657
311 989
618 972
201 871
349 507
241 262
284 940
331 591
149 512
140 384
127 389
101 317
419 786
752 795
343 801
300 734
631 967
14 27
179 796
147 996
413 846
414 598
23 369
778 848
61 287
339 795
54 968
405 433
28 934
583 876
27 723
503 873
585 837
852 854
111 887
653 834
60 787
133 606
310 339
923 934
926 978
791 989
551 556
20 74
354 567
98 250
23 501
494 782
775 939
240 689
27 364
431 548
124 578
798 892
552 992
214 529
221 582
220 546
153 676
460 494
314 784
168 493
832 971
20 131
107 315
51 97
50 106
168 969
687 855
349 405
39 929
384 907
864 987
219 596
11 959
590 705
480 830
154 414
398 626
48 697
244 812
156 440
275 890
372 439
45 844
392 452
1 839
476 595
280 753
677 687
440 748
803 989
358 421
743 908
417 940
402 440
221 937
149 541
141 254
519 672
197 327
522 531
855 864
26 735
201 556
479 558
499 742
289 707
91 671
112 639
564 887
3 88
183 964
159 869
18 298
67 891
457 721
152 744
393 806
230 837
17 126
137 811
312 842
12 471
551 763
229 896
423 953
545 935
228 242
316 615
256 553
54 994
451 623
205 935
143 527
292 815
316 490
504 887
218 372
827 881
179 186
85 662
2 380
224 503
433 550
252 418
10 776
226 514
355 952
398 802
341 825
2 720
205 495
200 880
316 699
206 410
302 340
161 849
623 892
194 833
115 922
671 800
737 756
166 711
818 956
87 663
206 614
616 784
303 880
164 816
10 450
165 474
812 932
66 264
575 817
282 484
752 874
245 496
633 653
532 643
321 387
227 650
175 556
328 629
533 812
218 796
151 909
360 961
453 851
312 691
852 881
501 548
94 910
142 234
458 625
240 372
407 733
414 741
124 278
282 966
366 779
271 478
358 626
1 997
106 417
530 819
295 763
571 823
487 581
174 281
137 698
30 551
521 987
866 946
101 340
452 775
44 833
316 462
821 988
256 702
294 713
356 443
293 698
458 583
6 508
378 401
330 805
315 645
712 807
52 272
202 518
151 806
209 431
171 936
27 578
346 487
283 810
73 505
430 525
22 930
161 445
179 385
346 797
713 797
674 771
352 775
268 946
230 759
786 847
43 653
101 984
164 419
192 564
20 306
528 952
539 732
249 462
701 813
169 882
151 632
431 764
281 785
439 566
26 802
276 580
269 421
315 909
266 317
881 893
239 629
289 603
419 440
137 631
86 431
339 584
109 870
167 781
315 394
532 903
618 848
190 991
121 369
180 461
75 319
156 637
203 311
630 994
261 505
33 244
31 382
24 134
133 653
333 650
638 939
451 806
472 535
307 740
0 910
208 308
109 652
355 604
6 755
473 971
278 483
64 249
334 427
52 138
480 596
92 823
363 780
173 314
227 352
495 664
653 834
426 874
510 939
484 874
58 766
475 677
226 568
148 669
230 613
267 518
333 571
26 903
300 833
471 542
278 984
638 991
8 933
133 713
94 248
495 777
372 965
0 188
249 289
18 751
283 302
245 876
67 748
7 538
140 480
149 605
624 695
500 869
127 817
383 967
180 928
18 673
639 780
420 836
185 433
318 928
873 996
57 275
494 811
416 435
731 737
176 328
88 879
30 829
21 402
375 586
352 950
500 836
311 830
127 804
377 462
258 639
527 838
62 669
611 907
192 311
762 963
119 734
436 939
324 823
5 415
556 987
659 839
197 601
829 931
596 763
506 994
58 183
296 330
534 824
266 356
1 28
142 712
689 810
571 858
400 753
382 383
160 298
502 883
405 834
693 792
299 950
116 427
256 272
126 262
264 469
28 941
171 818
86 491
817 887
184 250
240 357
6 934
818 887
571 641
387 534
264 513
427 994
405 533
283 361
1 410
188 843
342 985
851 963
385 412
626 907
821 897
201 333
359 783
74 242
536 801
229 913
282 934
182 306
344 956
611 740
515 587
226 612
104 848
63 139
128 705
505 649
322 399
135 919
235 292
456 666
185 424
584 717
446 953
249 385
787 945
72 599
516 842
50 558
290 529
193 757
541 721
452 619
89 585
45 605
135 292
120 244
542 590
40 325
169 941
768 917
687 836
315 651
45 447
476 586
741 812
79 191
322 754
377 979
219 472
109 977
590 616
220 862
103 251
162 781
496 822
375 585
278 867
344 586
641 893
184 840
335 932
171 388
733 790
86 563
143 228
310 449
654 678
487 862
981 998
259 576
617 863
550 869
96 462
629 966
297 708
159 960
165 626
79 82
138 593
149 544
357 676
190 608
824 943
366 741
135 831
82 471
417 585
369 452
781 892
196 368
531 774
895 946
145 229
410 508
236 848
42 992
545 869
635 640
98 862
172 465
303 853
288 584
247 926
133 898
153 667
235 302
225 401
221 497
1 215
4 536
23 126
119 663
536 666
15 742
15 223
71 948
318 560
221 916
362 480
288 657
604 746
113 139
57 215
398 522
108 664
85 992
0 448
786 904
584 757
44 410
339 381
228 440
775 867
148 953
324 410
654 910
149 577
108 210
331 471
172 705
265 883
405 434
178 273
697 844
709 714
290 546
498 677
723 847
330 583
708 767
333 967
172 818
773 896
541 600
39 691
210 917
493 673
388 927
83 268
237 685
345 415
303 945
334 452
671 676
442 969
228 917
306 401
294 833
771 848
808 890
323 964
365 407
242 362
39 219
187 337
281 540
675 708
337 497
418 649
430 922
402 798
518 749
448 626
675 774
215 217
83 522
26 325
385 404
205 751
306 680
540 758
191 537
140 601
16 826
236 869
611 734
470 969
===OUTPUT===
64637
===END===