{"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\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eIn dota2, there is a hero named Invoker. He has 3 basic skills in the game, which are Quas, Wex and Exort. Once he launches a basic skill, he will gain the corresponding element, where Quas gives \"Q\", Wex gives \"W\" and Exort gives \"E\".\u003c/p\u003e\u003cp\u003eInvoker can\u0027t have more than 3 elements simultaneously. If he launches a basic skill when he already owns 3 elements, he will get the corresponding element and lose the element he gained the earliest.\u003c/p\u003e\u003cp\u003eAs can be seen, there are 10 unordered combinations of 3 elements in 3 types, each represents a special skill, which are as follows:\u003c/p\u003e\u003cul\u003e \u003cli\u003e Cold Snap: unordered element combination \"QQQ\", denoted by \"Y\" \u003c/li\u003e\u003cli\u003e Ghost Walk: unordered element combination \"QQW\", denoted by \"V\" \u003c/li\u003e\u003cli\u003e Ice Wall: unordered element combination \"QQE\", denoted by \"G\" \u003c/li\u003e\u003cli\u003e EMP: unordered element combination \"WWW\", denoted by \"C\" \u003c/li\u003e\u003cli\u003e Tornado: unordered element combination \"QWW\", denoted by \"X\" \u003c/li\u003e\u003cli\u003e Alacrity: unordered element combination \"WWE\", denoted by \"Z\" \u003c/li\u003e\u003cli\u003e Sun Strike: unordered element combination \"EEE\", denoted by \"T\" \u003c/li\u003e\u003cli\u003e Forge Spirit: unordered element combination \"QEE\", denoted by \"F\" \u003c/li\u003e\u003cli\u003e Chaos Meteor: unordered element combination \"WEE\", denoted by \"D\" \u003c/li\u003e\u003cli\u003e Deafening Blast: unordered element combination \"QWE\", denoted by \"B\" \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eWhen Invoker owns 3 elements, he can launch the invoking skill, denoted by \"R\", to gain the special skill according to the elements he currently owns. After invoking, the elements won\u0027t disappear, and the chronological order of the 3 elements won\u0027t change.\u003c/p\u003e\u003cp\u003eNow given a sequence of special skills, you want to invoke them one by one with using the minimum number of basic skills(Q,W,E) and invoking skill(R). Print the minimum number in a single line.\u003c/p\u003e\u003cp\u003eAt the beginning, Invoker owns no elements. And you should re-invoke the special skills even if you have already invoked the same skills just now.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eInput a single line containing a string $$$s~(1\\le |s| \\le 100\\,000)$$$ that only contains uppercase letters in $$$\\{B,C,D,F,G,T,V,X,Y,Z\\}$$$, denoting the sequence of special skills.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput a single line containing a positive integer, denoting the minimum number of skills to launch.\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\u003eXDTBVV\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\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\u003eOne possible scheme is QWWREERERWQRQRR.\u003c/p\u003e\u003cp\u003e\u003c/p\u003e\u003ctable class\u003d\"tex-tabular\"\u003e\u003ctbody\u003e\u003ctr\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eQ\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eW\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eW\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eR\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eE\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eE\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eR\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eE\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eR\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eW\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eQ\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eR\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eQ\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eR\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eR\u003c/td\u003e\u003c/tr\u003e\u003ctr\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eQ\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eQW\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eQWW\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eX\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eWWE\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eWEE\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eD\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eEEE\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eT\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eEEW\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eEWQ\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eB\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eWQQ\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eV\u003c/td\u003e\u003ctd class\u003d\"tex-tabular-border-left tex-tabular-text-align-center tex-tabular-border-right tex-tabular-border-top tex-tabular-border-bottom\"\u003eV\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003cp\u003e\u003c/p\u003e"}}]}