{"raw_statement":[{"iden":"problem statement","content":"The string `20230322` can be rearranged into `02320232`, which is a repetition of `0232` twice.  \nSimilarly, a string consisting of digits is said to be **happy** when it can be rearranged into (or already is) a repetition of some string twice.  \nYou are given a string $S$ consisting of digits. Find the number of pairs of integers $(l,r)$ satisfying all of the following conditions.\n\n*   $1 \\le l \\le r \\le |S|$. ($|S|$ is the length of $S$.)\n*   The (contiguous) substring formed of the $l$\\-th through $r$\\-th characters of $S$ is happy."},{"iden":"constraints","content":"*   $S$ is a string consisting of digits whose length is between $1$ and $5 \\times 10^5$, inclusive."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$S$"},{"iden":"sample input 1","content":"20230322"},{"iden":"sample output 1","content":"4\n\nWe have $S=$ `20230322`.\nHere are the four pairs of integers $(l,r)$ that satisfy the condition: $(1,6)$, $(1,8)$, $(2,7)$, and $(7,8)$."},{"iden":"sample input 2","content":"0112223333444445555556666666777777778888888889999999999"},{"iden":"sample output 2","content":"185\n\n$S$ may begin with `0`."},{"iden":"sample input 3","content":"3141592653589793238462643383279502884197169399375105820974944"},{"iden":"sample output 3","content":"9"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}