200 2
857437555 1
878292433 1
1000000000 2
902877469 1
633169334 1
226561028 1
585072668 1
100044709 1
539199933 2
912422146 1
910646265 1
721366665 1
186603229 2
773292560 1
231350853 2
354503392 1
744903284 2
821756034 1
34298975 2
998984284 1
309346809 2
303874926 1
359780589 1
925374684 1
204361612 2
634085664 1
46345131 2
881232552 1
914356686 2
735169232 1
185093611 2
584793955 1
413140285 2
28737630 2
326711027 2
610958727 1
443222790 1
229310261 2
787184036 2
558394366 1
325066183 2
1000000000 2
537309466 2
438882609 2
36230811 1
735800689 2
3270347 2
562487528 2
493880562 1
368742375 2
664470798 2
296243417 2
605959348 2
262468536 2
639339417 2
392641579 2
787252757 2
402687520 2
63429143 2
787157117 1
141143679 1
585782724 1
503552209 1
354850913 1
513617648 2
858800211 1
435048640 2
610290935 1
928021686 2
266479194 2
728226455 2
1000000000 1
196042393 1
411075848 2
143699995 1
113608335 1
133111353 1
822516067 1
646338092 2
801665467 1
336694850 1
288498364 1
1000000000 2
526923689 2
999089582 2
417977811 2
268452823 2
739969205 2
227155836 2
1000000000 1
231595662 2
192064228 1
1000000000 2
749412988 2
168336766 2
962145189 1
233319383 1
329414988 2
97532564 2
239297789 1
849516739 1
896702214 1
626972897 2
430715701 1
408557221 2
2436725 1
520593938 1
582177922 1
755584302 1
550248673 2
477753407 1
961503823 1
933196675 1
529354874 2
68848777 2
117411172 2
962474009 2
812605433 2
74377349 1
141257116 2
1000000000 1
905554782 1
426012188 2
8831710 2
669105417 1
592706776 1
19740783 2
953179440 2
60197539 1
775684504 1
786704502 1
147292703 1
11583459 2
808469912 2
221684871 1
557416249 2
796034082 2
565159956 1
269836889 1
715173329 1
919892185 2
309742681 2
823926226 2
995404578 2
625206895 1
758408176 1
964607891 1
278408611 2
858276932 2
855597874 1
350067950 2
195060149 1
596001142 1
518392366 2
174312280 1
292045878 1
999515017 2
234235023 1
240239167 2
96830395 2
946771144 2
828761410 2
549741047 2
315484744 1
185603215 2
814548890 2
534615292 2
533138860 2
735209716 1
1000000000 2
153414056 2
1000000000 2
971225569 1
179821423 1
397900102 2
625472622 2
120348072 1
469560207 2
207483327 2
712186849 2
150026420 1
1000000000 2
642800671 1
711925958 2
42117274 1
711855799 2
260548300 1
957840486 1
539841537 1
336018191 1
916446532 2
20558760 1
649875393 1
771407381 2
551225238 1
978905775 2
794670048 2
626764937 2
793208247 1
199893026 2
00
00