/* package whatever; // don't place package name! */
 
import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	static int count = 0;
	static int maxDepth = 0;
	public static void main (String[] args) throws java.lang.Exception
	{
		for (int i = 1; i <= 7; i++)
			call(i);
 
	}
 
	static void call(int n) {
		count = 0;
		System.out.println("-------------");
		System.out.printf("tarai(%d,%d,0)%n",2*n,n);
		System.out.println(tarai(2*n,n,0,1));
		System.out.println("count: " + count);
		System.out.println("depth: " + maxDepth);
	}
 
	static int tarai(int x, int y, int z, int d) {
		count++;
		if (x <= y) {
			maxDepth = Math.max(maxDepth, d);
			return y;
		} else {
			return tarai(tarai(x-1,y,z,d+1),tarai(y-1,z,x,d+1),tarai(z-1,x,y,d+1),d+1);
		}
	}
}

LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKCXN0YXRpYyBpbnQgY291bnQgPSAwOwoJc3RhdGljIGludCBtYXhEZXB0aCA9IDA7CglwdWJsaWMgc3RhdGljIHZvaWQgbWFpbiAoU3RyaW5nW10gYXJncykgdGhyb3dzIGphdmEubGFuZy5FeGNlcHRpb24KCXsKCQlmb3IgKGludCBpID0gMTsgaSA8PSA3OyBpKyspCgkJCWNhbGwoaSk7CgkJCgl9CgkKCXN0YXRpYyB2b2lkIGNhbGwoaW50IG4pIHsKCQljb3VudCA9IDA7CgkJU3lzdGVtLm91dC5wcmludGxuKCItLS0tLS0tLS0tLS0tIik7CgkJU3lzdGVtLm91dC5wcmludGYoInRhcmFpKCVkLCVkLDApJW4iLDIqbixuKTsKCQlTeXN0ZW0ub3V0LnByaW50bG4odGFyYWkoMipuLG4sMCwxKSk7CgkJU3lzdGVtLm91dC5wcmludGxuKCJjb3VudDogIiArIGNvdW50KTsKCQlTeXN0ZW0ub3V0LnByaW50bG4oImRlcHRoOiAiICsgbWF4RGVwdGgpOwoJfQoJCglzdGF0aWMgaW50IHRhcmFpKGludCB4LCBpbnQgeSwgaW50IHosIGludCBkKSB7CgkJY291bnQrKzsKCQlpZiAoeCA8PSB5KSB7CgkJCW1heERlcHRoID0gTWF0aC5tYXgobWF4RGVwdGgsIGQpOwoJCQlyZXR1cm4geTsKCQl9IGVsc2UgewoJCQlyZXR1cm4gdGFyYWkodGFyYWkoeC0xLHkseixkKzEpLHRhcmFpKHktMSx6LHgsZCsxKSx0YXJhaSh6LTEseCx5LGQrMSksZCsxKTsKCQl9Cgl9Cn0=