{"raw_statement":[{"iden":"statement","content":"The great dog detective Sherlock Bones is on the verge of a new discovery. But for this problem, he needs the help of his most trusted advisor -you- to help him fetch the answer to this case.\n\nHe is given a string of zeros and ones and length N.\n\nLet F(x, y) equal to the number of ones in the string between indices x and y inclusively.\n\nYour task is to help Sherlock Bones find the number of ways to choose indices (i, j, k) such that i < j < k, sj is equal to 1, and F(i, j) is equal to F(j, k).\n\nThe first line of input is T – the number of test cases.\n\nThe first line of each test case is an integer N (3 ≤ N ≤ 2 × 105).\n\nThe second line is a string of zeros and ones of length N.\n\nFor each test case, output a line containing a single integer- the number of ways to choose indices (i, j, k).\n\n"},{"iden":"input","content":"The first line of input is T – the number of test cases.The first line of each test case is an integer N (3 ≤ N ≤ 2 × 105).The second line is a string of zeros and ones of length N."},{"iden":"output","content":"For each test case, output a line containing a single integer- the number of ways to choose indices (i, j, k)."}],"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 $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 2 \\times 10^5 $, and let $ s = s_1 s_2 \\dots s_n \\in \\{0,1\\}^n $ be a binary string.  \nDefine $ F(i, j) = \\sum_{\\ell=i}^{j} s_\\ell $ for $ 1 \\leq i \\leq j \\leq n $.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq \\text{unknown} $ (not bounded in input, but implied by constraints on $ n $)  \n2. For each test case:  \n   - $ 3 \\leq n \\leq 2 \\times 10^5 $  \n   - $ s_i \\in \\{0,1\\} $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCount the number of ordered triples $ (i, j, k) $ such that:  \n- $ 1 \\leq i < j < k \\leq n $,  \n- $ s_j = 1 $,  \n- $ F(i, j) = F(j, k) $.","simple_statement":"Given a binary string of length N, count the number of triples (i, j, k) such that i < j < k, s[j] = '1', and the number of ones from i to j equals the number of ones from j to k.","has_page_source":false}