{"raw_statement":[{"iden":"statement","content":"During the SCPC2015 celebration, and as Noura likes to keep everyone entertained, she wanted to play a game with the students and volunteers. She asked them to stand in a circle in order to assign them into 2 groups.\n\nThe rules for forming the two groups are: \n\nGiven a string that you should treat as a circle (which means that the last letter is a neighbor to the first one), calculate the number of ways to choose two ordered, non - overlapping substrings that represent the two groups and satisfy the given rules.\n\nThe first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.\n\nEach test case will consist of a single line that contains a string S (2 ≤ |S| ≤ 104).\n\n|S| represents the length of the string S.\n\nFor each test case, print the number of ways on a single line.\n\nWarning: large Input/Output data, be careful with certain languages.\n\n"},{"iden":"input","content":"The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.Each test case will consist of a single line that contains a string S (2 ≤ |S| ≤ 104).|S| represents the length of the string S."},{"iden":"output","content":"For each test case, print the number of ways on a single line."},{"iden":"examples","content":"Input3AbBAcMsCpCsyriaOutput836100"},{"iden":"note","content":"Warning: large Input/Output data, be careful with certain languages."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ S = s_0 s_1 \\dots s_{n-1} $ be a string of length $ n = |S| $, with indices taken modulo $ n $ (circular string).  \n\n**Constraints**  \n1. $ 1 \\leq T \\leq 256 $  \n2. For each test case: $ 2 \\leq n \\leq 10^4 $  \n\n**Objective**  \nCount the number of ordered pairs $ (U, V) $ of non-overlapping substrings of $ S $ (treated circularly), such that:  \n- $ U $ and $ V $ are contiguous substrings of $ S $,  \n- $ U \\cap V = \\emptyset $ (no shared character positions in the circular string),  \n- The substrings are **ordered**: $ (U, V) \\neq (V, U) $ if $ U \\neq V $,  \n- Each substring has length at least 1.  \n\nFormally, let $ U = S[i:i+\\ell_1] $, $ V = S[j:j+\\ell_2] $, with $ \\ell_1, \\ell_2 \\geq 1 $, and the sets of indices $ \\{i, i+1, \\dots, i+\\ell_1-1\\} \\mod n $ and $ \\{j, j+1, \\dots, j+\\ell_2-1\\} \\mod n $ are disjoint.  \nCount all such distinct ordered pairs $ (U, V) $.","simple_statement":"Given a circular string, count the number of ways to choose two non-overlapping, ordered substrings as two groups.","has_page_source":false}