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