Read problems statements in Russian here 
Polo, the Penguin, likes lucky strings - the strings that consist only of lucky digits 4 and 7.
He has a lucky string S. Digits in this string are numbered from left to right starting with 1. He performs the following operations on the string while it is possible to do so:

Find a set of all positions, P, such that for every position i in P, S[i] = 4 and S[i+1] = 7. (For example, if S = 744744747, then P = {3, 6, 8}.) Add all elements in P to the result. If there is no such position, then STOP. 
Erase all digits in string S with positions i and i + 1 for all i in the set P. After erasing all such digits from S repeat Step 1. (For example, the new S = 744)

Find the result that he will get at the end.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of the string S. The second line contains the lucky string S.

------ Output ------ 

For each test case, output a single line containing the answer to the corresponding test case.

------ Constraints ------ 

$1 ≤ T ≤ 100,000$
$1 ≤ |S| ≤ 100,000$
$The total length of all strings will not exceed 100,000$

------ Example ------ 

Input:
2
4
4747
10
4447477747
  
Output:
4
20

------   ------ 

------ Explanation ------ 

Example case 1. In this case, there is just a single iteration. Since P = {1, 3}, the answer is 1 + 3 = 4.
Example case 2. In this case, there are three iterations. On the first iteration P = {3, 5, 9}. On the second iteration S = 4477, P = {2}. On the third iteration S = 47, P = {1}. So the answer is 3 + 5 + 9 + 2 + 1 = 20.

Source: codechef | Difficulty: VERY_HARD
Tags: Data structures

Range queries

Segment trees revisited


Solutions:
import sys

class LuckyStars:
	bit = []
	n = 0

	def update(self, i, v):
		global bit
		global n
		i += 1
		while i <= n:
			bit[i] += 1
			i += i & -i

	def query(self, i):
		global bit
		global n
		r = 0
		i += 1
		while i:
			r += bit[i]
			i -= i & -i
		return r

	def solve(self, ls):
		global bit
		global n
		n = len(ls)
		stack = []
		time = [None] * n
		for (i, j) in enumerate(ls):
			if j == '7':
				if stack and stack[-1][0] == '4':
					(_, k, t) = stack.pop()
					time[k] = t
					if stack and stack[-1][0] == '4':
						stack[-1][-1] = max(stack[-1][-1], t + 1)
				else:
					stack.append([j, i, 0])
			else:
				stack.append([j, i, 0])
		bit = [0] * (n + 1)
		res = 0
		for (i, j) in enumerate(time, 1):
			if j != None:
				res += i - 2 * self.query(j - 1)
				self.update(j, 1)
		return res
cases = int(sys.stdin.readline().strip())
solver = LuckyStars()
results = []
for _ in range(cases):
	length = int(sys.stdin.readline().strip())
	lucky_string = sys.stdin.readline().strip()
	results.append(solver.solve(lucky_string))
for result in results:
	print(result)