{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eMike has many friends. Here are nine of them: Alice, Bob, Carol, Dave, Eve, Frank, Gloria, Henry and Irene. \u003cbr\u003e\u003cbr\u003eMike is so skillful that he can master $n$ languages (aka. programming languages).\u003cbr\u003e\u003cbr\u003eHis nine friends are all weaker than he. The sets they can master are all subsets of Mike\u0027s languages.\u003cbr\u003e\u003cbr\u003eBut the relations between the nine friends is very complex. Here are some clues.\u003cbr\u003e\u003cbr\u003e1. Alice is a nice girl, so her subset is a superset of Bob\u0027s.\u003cbr\u003e2. Bob is a naughty boy, so his subset is a superset of Carol\u0027s.\u003cbr\u003e3. Dave is a handsome boy, so his subset is a superset of Eve\u0027s.\u003cbr\u003e4. Eve is an evil girl, so her subset is a superset of Frank\u0027s.\u003cbr\u003e5. Gloria is a cute girl, so her subset is a superset of Henry\u0027s.\u003cbr\u003e6. Henry is a tall boy, so his subset is a superset of Irene\u0027s.\u003cbr\u003e7. Alice is a nice girl, so her subset is a superset of Eve\u0027s.\u003cbr\u003e8. Eve is an evil girl, so her subset is a superset of Carol\u0027s.\u003cbr\u003e9. Dave is a handsome boy, so his subset is a superset of Gloria\u0027s.\u003cbr\u003e10. Gloria is a cute girl, so her subset is a superset of Frank\u0027s.\u003cbr\u003e11. Gloria is a cute girl, so her subset is a superset of Bob\u0027s.\u003cbr\u003e\u003cbr\u003eNow Mike wants to know, how many situations there might be.\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $T$($T \\le 20$) denoting the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line contains an integer $n$($0\\leq n\\leq 3000$), denoting the number of languages.\u003cbr\u003e\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output \u0027\u0027Case #t:\u0027\u0027 to represent this is the t-th case. And then output the answer.\u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n0\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1\r\nCase #2: 1024\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}