There are N equidistant points on the circumference of a circle. A few of these points are blocked. The rest of the points are active. As we know, we need 3 points to make a triangle. In this problem, to make a valid triangle, at least one of the vertices should be active. You have to count the number of pairs of valid triangles having equal area using the N points on the circle. The angular distance between the points is 2*pi/N since they are equidistant.

INPUT

The first line of input has an integer T, the number of test cases. T test cases follow. First line of each test case has an integer N, the number of points. The next line has a string composed of 0 or 1 for each point. 0 means the point is blocked while 1 means it is active.

OUTPUT

For each test case, you have to output an integer giving the number of pairs of valid triangles possible in each line.