{"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\"\u003eJerry likes dogs. He has $N$ dogs numbered $0, 1, ..., N-1$. He also has $N$ cages numbered $0, 1, ..., N-1$. Everyday he takes all his dogs out and walks them outside. When he is back home, as dogs can’t recognize the numbers, each dog just randomly selects a cage and enters it. Each cage can hold only one dog.\u003cbr\u003eOne day, Jerry noticed that some dogs were in the cage with the same number of themselves while others were not. Jerry would like to know what’s the expected number of dogs that are NOT in the cage with the same number of themselves.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input gives the number of test cases, $T$. $T$ test cases follow.\u003cbr\u003eEach test case contains only one number $N$, indicating the number of dogs and cages.\u003cbr\u003e$1 \\leq T \\leq 10^5$\u003cbr\u003e$1 \\leq N \\leq 10^5$"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line containing “Case #x: y”, where $x$ is the test case number (starting from 1) and $y$ is the expected number of dogs that are NOT in the cage with the same number of itself.\u003cbr\u003e$y$ will be considered correct if it is within an absolute or relative error of $10^{-6}$ of the correct answer."}},{"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\n1\r\n2\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 0.0000000000\r\nCase #2: 1.0000000000\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eIn the first test case, the only dog will enter the only cage. So the answer is 0.\u003cbr\u003eIn the second test case, if the first dog enters the cage of the same number, both dogs are in the cage of the same number, \u003cbr\u003ethe number of mismatch is 0. If both dogs are not in the cage with the same number of itself, the number of mismatch is 2. \u003cbr\u003eSo the expected number is (0+2)/2\u003d1."}}]}