{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eVasya came up with a password to register for \u003cspan class\u003d\"tex-font-style-it\"\u003eEatForces\u003c/span\u003e — a string $$$s$$$. The password in \u003cspan class\u003d\"tex-font-style-it\"\u003eEatForces\u003c/span\u003e should be a string, consisting of lowercase and uppercase Latin letters and digits.\u003c/p\u003e\u003cp\u003eBut since \u003cspan class\u003d\"tex-font-style-it\"\u003eEatForces\u003c/span\u003e takes care of the security of its users, user passwords must contain at least one digit, at least one uppercase Latin letter and at least one lowercase Latin letter. For example, the passwords \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eabaCABA12\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eZ7q\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e3R24m\u003c/span\u003e\" are valid, and the passwords \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eqwerty\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eqwerty12345\u003c/span\u003e\" and \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ePassword\u003c/span\u003e\" are not. \u003c/p\u003e\u003cp\u003eA substring of string $$$s$$$ is a string $$$x \u003d s_l s_{l + 1} \\dots s_{l + len - 1} (1 \\le l \\le |s|, 0 \\le len \\le |s| - l + 1)$$$. $$$len$$$ is the length of the substring. Note that the empty string is also considered a substring of $$$s$$$, it has the length $$$0$$$.\u003c/p\u003e\u003cp\u003eVasya\u0027s password, however, may come too weak for the security settings of \u003cspan class\u003d\"tex-font-style-it\"\u003eEatForces\u003c/span\u003e. He likes his password, so he wants to replace some its substring with another string of the same length in order to satisfy the above conditions. This operation should be performed \u003cspan class\u003d\"tex-font-style-bf\"\u003eexactly\u003c/span\u003e once, and \u003cspan class\u003d\"tex-font-style-bf\"\u003ethe chosen string should have the minimal possible length\u003c/span\u003e.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eNote that the length of $$$s$$$ should not change after the replacement of the substring, and the string itself should contain only lowercase and uppercase Latin letters and digits.\u003c/span\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains a single integer $$$T$$$ ($$$1 \\le T \\le 100$$$) — the number of testcases.\u003c/p\u003e\u003cp\u003eEach of the next $$$T$$$ lines contains the initial password $$$s~(3 \\le |s| \\le 100)$$$, consisting of lowercase and uppercase Latin letters and digits.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eOnly $$$T \u003d 1$$$ is allowed for hacks\u003c/span\u003e.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each testcase print a renewed password, which corresponds to given conditions. \u003c/p\u003e\u003cp\u003eThe length of the replaced substring is calculated as following: write down all the changed positions. If there are none, then the length is $$$0$$$. Otherwise the length is the difference between the first and the last changed position plus one. For example, the length of the changed substring between the passwords \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eabcdef\u003c/span\u003e\" $$$\\rightarrow$$$ \"\u003cspan class\u003d\"tex-font-style-tt\"\u003ea7cdEf\u003c/span\u003e\" is $$$4$$$, because the changed positions are $$$2$$$ and $$$5$$$, thus $$$(5 - 2) + 1 \u003d 4$$$.\u003c/p\u003e\u003cp\u003e\u003cspan class\u003d\"tex-font-style-bf\"\u003eIt is guaranteed that such a password always exists.\u003c/span\u003e\u003c/p\u003e\u003cp\u003eIf there are several suitable passwords — output any of them.\u003c/p\u003e"}},{"title":"Examples","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\nabcDCE\nhtQw27\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eabcD4E\nhtQw27\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first example Vasya\u0027s password lacks a digit, he replaces substring \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eC\u003c/span\u003e\" with \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e4\u003c/span\u003e\" and gets password \"abcD4E\". That means, he changed the substring of length 1.\u003c/p\u003e\u003cp\u003eIn the second example Vasya\u0027s password is ok from the beginning, and nothing has to be changed. That is the same as replacing the empty substring with another empty substring (length 0).\u003c/p\u003e"}}]}