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