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