Given a string $s$.
You can perform the following operation on given string any number of time.
Delete two successive elements of the string if they are same.
After performing the above operation you have to return the least possible length of the string.

-----Input:-----
- First line will contain $T$, number of testcases. Then the testcases follow. 
- Each testcase contains of a single line of input, a string $s$. 

-----Output:-----
For each testcase, output in a single line answer- minimum length of string possible after performing given operations.

-----Constraints-----
- $1 \leq T \leq 1000$
- $2 \leq length of string \leq 10^5$
$s$ contains only lowercase letters.

-----Sample Input:-----
3
abccd
abbac
aaaa

-----Sample Output:-----
3
1
0

-----EXPLANATION:-----
- In first case, $"abd"$ will be final string.
- in second case, $"c"$ will be final string

Difficulty: interview

Starter code:

Solutions:
from sys import stdin,stdout
import math,bisect
from datetime import date
from collections import Counter,deque,defaultdict
L=lambda:list(map(int, stdin.readline().strip().split()))
M=lambda:list(map(int, stdin.readline().strip().split()))
I=lambda:int(stdin.readline().strip())
S=lambda:stdin.readline().strip()
C=lambda:stdin.readline().strip().split()
def pr(a):return("".join(list(map(str,a))))
#_________________________________________________#

def solve():
    s = list(S())
    a=[s[0]]
    for i in range(1,len(s)):
        if a and a[-1]==s[i]:
            a.pop()
        else:
            a.append(s[i])
    print(len(a))
    
for _ in range(I()): 
    solve()


for _ in range(int(input())):
    inps = input().strip()
    stck = [inps[0]]
    for i in range(1, len(inps)):
        if len(stck) > 0:
            if inps[i] == stck[-1]:
                stck.pop()
            else:
                stck.append(inps[i])
        else:
            stck.append(inps[i])
    print(len(stck))