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