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