package gcj2013.template;
 
import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
 
import static java.
util.
Arrays.
deepToString;  
public class Template2 
implements Runnable { 	private static final char PROB = Template2.class.getSimpleName().charAt(0);
	private static int DEFAULT_PARARELL 
= Runtime.
getRuntime().
availableProcessors() + 1; 	private static File DIR 
= new File("."); 	private static boolean TEST_ALL = false;
 
	public static class Solver implements Callable<String> {
		private static final double EPS = 1e-12;
		private static final int INF = 1 << 20;
		private static final int[] di = { -1, 0, 0, 1 };
		private static final int[] dj = { 0, -1, 1, 0 };
 
		// shared table
		static {
			// :TODO
		}
 
		// parse
		public Solver(final Scanner sc) {
			// :TODO
		}
 
		// solve
		@Override
			// :TODO
			throw null;
		}
	}
 
	// Template
	@Override
	public void run() {
		final ExecutorService es = Executors.newFixedThreadPool(DEFAULT_PARARELL);
		try (final Scanner sc 
= new Scanner
(System.
in)) { 			final List<Future<String>> list = new ArrayList<>();
			final int T = sc.nextInt();
			for (int i = 0; i < T; i++)
				list.add(es.submit(new Solver(sc)));
			for (int t = 1; t <= T; t++) {
				debugf("Case #%s%n", t);
				System.
out.
printf("Case #%s: %s%n", t, list.
get(t 
- 1).
get()); 			}
			debug("done.");
			e.printStackTrace();
		}
		es.shutdown();
	}
 
		if (TEST_ALL) {
			for (final String input 
: seekInputFiles
()) { 				debug("INPUT", input);
				new Template2().run();
			}
		} else {
			final String input 
= seekInputFile
(); 			debug("INPUT", input);
			if (input != null) {
			} else
				DEFAULT_PARARELL = 1;
			new Template2().run();
		}
	}
 
	private static String seekInputFile
() { 		final String[] names 
= new String[] { PROB 
+ "-large-practice-2.in", PROB 
+ "-large-practice-1.in",
 				PROB + "-large-practice.in", PROB + "-large-2.in", PROB + "-large-1.in", PROB + "-large.in",
				PROB + "-small-practice-2.in", PROB + "-small-practice-1.in", PROB + "-small-practice.in" };
			if (new File(DIR, s
).
exists()) 				return s;
		for (int k = 2; k >= 0; k--) {
			int max = -1;
			for (int i 
= 0; new File(DIR, PROB 
+ "-small" + (k 
> 0 ? "-" + k 
: "") + "-attempt" + i 
+ ".in").
exists(); i
++) 				max = i;
			if (max >= 0)
				return PROB + "-small" + (k > 0 ? "-" + k : "") + "-attempt" + max + ".in";
		}
		return null;
	}
 
	private static List<String> seekInputFiles() {
		final List<String> ret = new ArrayList<>();
		final String[] names 
= new String[] { PROB 
+ "-large-practice-2.in", PROB 
+ "-large-practice-1.in",
 				PROB + "-large-practice.in", PROB + "-large-2.in", PROB + "-large-1.in", PROB + "-large.in",
				PROB + "-small-practice-2.in", PROB + "-small-practice-1.in", PROB + "-small-practice.in" };
			if (new File(DIR, s
).
exists()) 				ret.add(s);
		for (int k = 2; k >= 0; k--) {
			int max = -1;
			for (int i 
= 0; new File(DIR, PROB 
+ "-small" + (k 
> 0 ? "-" + k 
: "") + "-attempt" + i 
+ ".in").
exists(); i
++) 				max = i;
			if (max >= 0)
				ret.add(PROB + "-small" + (k > 0 ? "-" + k : "") + "-attempt" + max + ".in");
		}
		return ret;
	}
 
		System.
err.
printf(format, os
); 	}
 
	private static void debug
(Object... 
os) { 		System.
err.
println(deepToString
(os
)); 	}
}
 
				cGFja2FnZSBnY2oyMDEzLnRlbXBsYXRlOwoKaW1wb3J0IGphdmEuaW8uKjsKaW1wb3J0IGphdmEudXRpbC5BcnJheUxpc3Q7CmltcG9ydCBqYXZhLnV0aWwuTGlzdDsKaW1wb3J0IGphdmEudXRpbC5TY2FubmVyOwppbXBvcnQgamF2YS51dGlsLmNvbmN1cnJlbnQuQ2FsbGFibGU7CmltcG9ydCBqYXZhLnV0aWwuY29uY3VycmVudC5FeGVjdXRvclNlcnZpY2U7CmltcG9ydCBqYXZhLnV0aWwuY29uY3VycmVudC5FeGVjdXRvcnM7CmltcG9ydCBqYXZhLnV0aWwuY29uY3VycmVudC5GdXR1cmU7CgppbXBvcnQgc3RhdGljIGphdmEudXRpbC5BcnJheXMuZGVlcFRvU3RyaW5nOwoKcHVibGljIGNsYXNzIFRlbXBsYXRlMiBpbXBsZW1lbnRzIFJ1bm5hYmxlIHsKCXByaXZhdGUgc3RhdGljIGZpbmFsIGNoYXIgUFJPQiA9IFRlbXBsYXRlMi5jbGFzcy5nZXRTaW1wbGVOYW1lKCkuY2hhckF0KDApOwoJcHJpdmF0ZSBzdGF0aWMgaW50IERFRkFVTFRfUEFSQVJFTEwgPSBSdW50aW1lLmdldFJ1bnRpbWUoKS5hdmFpbGFibGVQcm9jZXNzb3JzKCkgKyAxOwoJcHJpdmF0ZSBzdGF0aWMgRmlsZSBESVIgPSBuZXcgRmlsZSgiLiIpOwoJcHJpdmF0ZSBzdGF0aWMgYm9vbGVhbiBURVNUX0FMTCA9IGZhbHNlOwoKCXB1YmxpYyBzdGF0aWMgY2xhc3MgU29sdmVyIGltcGxlbWVudHMgQ2FsbGFibGU8U3RyaW5nPiB7CgkJcHJpdmF0ZSBzdGF0aWMgZmluYWwgZG91YmxlIEVQUyA9IDFlLTEyOwoJCXByaXZhdGUgc3RhdGljIGZpbmFsIGludCBJTkYgPSAxIDw8IDIwOwoJCXByaXZhdGUgc3RhdGljIGZpbmFsIGludFtdIGRpID0geyAtMSwgMCwgMCwgMSB9OwoJCXByaXZhdGUgc3RhdGljIGZpbmFsIGludFtdIGRqID0geyAwLCAtMSwgMSwgMCB9OwoKCQkvLyBzaGFyZWQgdGFibGUKCQlzdGF0aWMgewoJCQkvLyA6VE9ETwoJCX0KCgkJLy8gcGFyc2UKCQlwdWJsaWMgU29sdmVyKGZpbmFsIFNjYW5uZXIgc2MpIHsKCQkJLy8gOlRPRE8KCQl9CgoJCS8vIHNvbHZlCgkJQE92ZXJyaWRlCgkJcHVibGljIFN0cmluZyBjYWxsKCkgewoJCQkvLyA6VE9ETwoJCQl0aHJvdyBudWxsOwoJCX0KCX0KCgkvLyBUZW1wbGF0ZQoJQE92ZXJyaWRlCglwdWJsaWMgdm9pZCBydW4oKSB7CgkJZmluYWwgRXhlY3V0b3JTZXJ2aWNlIGVzID0gRXhlY3V0b3JzLm5ld0ZpeGVkVGhyZWFkUG9vbChERUZBVUxUX1BBUkFSRUxMKTsKCQl0cnkgKGZpbmFsIFNjYW5uZXIgc2MgPSBuZXcgU2Nhbm5lcihTeXN0ZW0uaW4pKSB7CgkJCWZpbmFsIExpc3Q8RnV0dXJlPFN0cmluZz4+IGxpc3QgPSBuZXcgQXJyYXlMaXN0PD4oKTsKCQkJZmluYWwgaW50IFQgPSBzYy5uZXh0SW50KCk7CgkJCWZvciAoaW50IGkgPSAwOyBpIDwgVDsgaSsrKQoJCQkJbGlzdC5hZGQoZXMuc3VibWl0KG5ldyBTb2x2ZXIoc2MpKSk7CgkJCWZvciAoaW50IHQgPSAxOyB0IDw9IFQ7IHQrKykgewoJCQkJZGVidWdmKCJDYXNlICMlcyVuIiwgdCk7CgkJCQlTeXN0ZW0ub3V0LnByaW50ZigiQ2FzZSAjJXM6ICVzJW4iLCB0LCBsaXN0LmdldCh0IC0gMSkuZ2V0KCkpOwoJCQkJU3lzdGVtLmdjKCk7CgkJCX0KCQkJZGVidWcoImRvbmUuIik7CgkJfSBjYXRjaCAoRXhjZXB0aW9uIGUpIHsKCQkJZS5wcmludFN0YWNrVHJhY2UoKTsKCQl9CgkJZXMuc2h1dGRvd24oKTsKCX0KCglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbihTdHJpbmcuLi4gYXJncykgdGhyb3dzIElPRXhjZXB0aW9uIHsKCQlpZiAoVEVTVF9BTEwpIHsKCQkJZm9yIChmaW5hbCBTdHJpbmcgaW5wdXQgOiBzZWVrSW5wdXRGaWxlcygpKSB7CgkJCQlkZWJ1ZygiSU5QVVQiLCBpbnB1dCk7CgkJCQlTeXN0ZW0uc2V0SW4obmV3IEJ1ZmZlcmVkSW5wdXRTdHJlYW0obmV3IEZpbGVJbnB1dFN0cmVhbShuZXcgRmlsZShESVIsIGlucHV0KSkpKTsKCQkJCVN5c3RlbS5zZXRPdXQobmV3IFByaW50U3RyZWFtKGlucHV0ICsgIi5vdXQiKSk7CgkJCQluZXcgVGVtcGxhdGUyKCkucnVuKCk7CgkJCX0KCQl9IGVsc2UgewoJCQlmaW5hbCBTdHJpbmcgaW5wdXQgPSBzZWVrSW5wdXRGaWxlKCk7CgkJCWRlYnVnKCJJTlBVVCIsIGlucHV0KTsKCQkJaWYgKGlucHV0ICE9IG51bGwpIHsKCQkJCVN5c3RlbS5zZXRJbihuZXcgQnVmZmVyZWRJbnB1dFN0cmVhbShuZXcgRmlsZUlucHV0U3RyZWFtKG5ldyBGaWxlKERJUiwgaW5wdXQpKSkpOwoJCQkJU3lzdGVtLnNldE91dChuZXcgUHJpbnRTdHJlYW0oaW5wdXQgKyAiLm91dCIpKTsKCQkJfSBlbHNlCgkJCQlERUZBVUxUX1BBUkFSRUxMID0gMTsKCQkJbmV3IFRlbXBsYXRlMigpLnJ1bigpOwoJCX0KCX0KCglwcml2YXRlIHN0YXRpYyBTdHJpbmcgc2Vla0lucHV0RmlsZSgpIHsKCQlmaW5hbCBTdHJpbmdbXSBuYW1lcyA9IG5ldyBTdHJpbmdbXSB7IFBST0IgKyAiLWxhcmdlLXByYWN0aWNlLTIuaW4iLCBQUk9CICsgIi1sYXJnZS1wcmFjdGljZS0xLmluIiwKCQkJCVBST0IgKyAiLWxhcmdlLXByYWN0aWNlLmluIiwgUFJPQiArICItbGFyZ2UtMi5pbiIsIFBST0IgKyAiLWxhcmdlLTEuaW4iLCBQUk9CICsgIi1sYXJnZS5pbiIsCgkJCQlQUk9CICsgIi1zbWFsbC1wcmFjdGljZS0yLmluIiwgUFJPQiArICItc21hbGwtcHJhY3RpY2UtMS5pbiIsIFBST0IgKyAiLXNtYWxsLXByYWN0aWNlLmluIiB9OwoJCWZvciAoZmluYWwgU3RyaW5nIHMgOiBuYW1lcykKCQkJaWYgKG5ldyBGaWxlKERJUiwgcykuZXhpc3RzKCkpCgkJCQlyZXR1cm4gczsKCQlmb3IgKGludCBrID0gMjsgayA+PSAwOyBrLS0pIHsKCQkJaW50IG1heCA9IC0xOwoJCQlmb3IgKGludCBpID0gMDsgbmV3IEZpbGUoRElSLCBQUk9CICsgIi1zbWFsbCIgKyAoayA+IDAgPyAiLSIgKyBrIDogIiIpICsgIi1hdHRlbXB0IiArIGkgKyAiLmluIikuZXhpc3RzKCk7IGkrKykKCQkJCW1heCA9IGk7CgkJCWlmIChtYXggPj0gMCkKCQkJCXJldHVybiBQUk9CICsgIi1zbWFsbCIgKyAoayA+IDAgPyAiLSIgKyBrIDogIiIpICsgIi1hdHRlbXB0IiArIG1heCArICIuaW4iOwoJCX0KCQlyZXR1cm4gbnVsbDsKCX0KCglwcml2YXRlIHN0YXRpYyBMaXN0PFN0cmluZz4gc2Vla0lucHV0RmlsZXMoKSB7CgkJZmluYWwgTGlzdDxTdHJpbmc+IHJldCA9IG5ldyBBcnJheUxpc3Q8PigpOwoJCWZpbmFsIFN0cmluZ1tdIG5hbWVzID0gbmV3IFN0cmluZ1tdIHsgUFJPQiArICItbGFyZ2UtcHJhY3RpY2UtMi5pbiIsIFBST0IgKyAiLWxhcmdlLXByYWN0aWNlLTEuaW4iLAoJCQkJUFJPQiArICItbGFyZ2UtcHJhY3RpY2UuaW4iLCBQUk9CICsgIi1sYXJnZS0yLmluIiwgUFJPQiArICItbGFyZ2UtMS5pbiIsIFBST0IgKyAiLWxhcmdlLmluIiwKCQkJCVBST0IgKyAiLXNtYWxsLXByYWN0aWNlLTIuaW4iLCBQUk9CICsgIi1zbWFsbC1wcmFjdGljZS0xLmluIiwgUFJPQiArICItc21hbGwtcHJhY3RpY2UuaW4iIH07CgkJZm9yIChmaW5hbCBTdHJpbmcgcyA6IG5hbWVzKQoJCQlpZiAobmV3IEZpbGUoRElSLCBzKS5leGlzdHMoKSkKCQkJCXJldC5hZGQocyk7CgkJZm9yIChpbnQgayA9IDI7IGsgPj0gMDsgay0tKSB7CgkJCWludCBtYXggPSAtMTsKCQkJZm9yIChpbnQgaSA9IDA7IG5ldyBGaWxlKERJUiwgUFJPQiArICItc21hbGwiICsgKGsgPiAwID8gIi0iICsgayA6ICIiKSArICItYXR0ZW1wdCIgKyBpICsgIi5pbiIpLmV4aXN0cygpOyBpKyspCgkJCQltYXggPSBpOwoJCQlpZiAobWF4ID49IDApCgkJCQlyZXQuYWRkKFBST0IgKyAiLXNtYWxsIiArIChrID4gMCA/ICItIiArIGsgOiAiIikgKyAiLWF0dGVtcHQiICsgbWF4ICsgIi5pbiIpOwoJCX0KCQlyZXR1cm4gcmV0OwoJfQoKCXByaXZhdGUgc3RhdGljIHZvaWQgZGVidWdmKFN0cmluZyBmb3JtYXQsIE9iamVjdC4uLiBvcykgewoJCVN5c3RlbS5lcnIucHJpbnRmKGZvcm1hdCwgb3MpOwoJfQoKCXByaXZhdGUgc3RhdGljIHZvaWQgZGVidWcoT2JqZWN0Li4uIG9zKSB7CgkJU3lzdGVtLmVyci5wcmludGxuKGRlZXBUb1N0cmluZyhvcykpOwoJfQp9Cg==