Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###


# class Point():
#   def __init__(self, x, y):
#     self.x = x
#     self.y = y
  
#   def __str__(self):
#     # return f"Point(x={self.x}, y={self.y})"
#     return "Point(x=" + str(self.x) + ", y=" + str(self.y) + ")"

#   def __repr__(self):
#     return self.__str__()

def parse():
  H, W = map(int, input().split(" "))
  grid = []
  for h in range(H):
    grid.append(list(input()))
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for y in range(H):
    print(grid[y])

def is_all_black(grid):
  H = len(grid)
  W = len(grid[0])
  for y in range(H):
    for x in range(W):
      if grid[y][x] == ".": return False
  return True

def main():
  H, W, grid = parse()
  # print(H, W, grid)

  # vecs = [Point(0, -1), Point(0, 1), Point(-1, 0), Point(1, 0)]
  vecs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
  
  # 初期の黒色の場所を追加
  black_points = []
  for y in range(H):
    for x in range(W):
      if grid[y][x] == "#":
        black_points.append((x, y))
        # black_points.append(Point(x, y))

  ans = 0
  while len(black_points) > 0:
  # while not is_all_black(grid):
    next_black_points = []
    for black_point in black_points:
      # print("black_point:", black_point)
      for vec in vecs:
        x = black_point[0] + vec[0]
        y = black_point[1] + vec[1]
        # target_point = Point(black_point.x + vec.x, black_point.y + vec.y)
        if x < 0 or y < 0 or x >= W or y >= H or grid[y][x] == "#": continue
        grid[y][x] = "#"
        next_black_points.append((x, y))
    black_points = next_black_points
    ans += 1

    # print("next_black_points:", next_black_points)
    # print_grid(grid)
    # input()
  
  print(ans - 1)

if __name__ == "__main__":
  main()

### FIXED CODE ###


import numpy as np

def parse():
  H, W = map(int, input().split(" "))
  grid = [list(input()) for y in range(H)]
  return H, W, grid

def print_grid(grid):
  H = len(grid)
  print("grid:")
  for line in grid:
    for c in line:
      print(c, end="")
    print("")

def main():
  H, W, grid = parse()
  # print(H, W)
  # print_grid(grid)

  # visited = [[W * H if grid[y][x] == "." else 0 for x in range(W)] for y in range(H)]
  visited = np.zeros((H, W), int)
  for y in range(H):
    # visited.append([])
    for x in range(W):
      if grid[y][x] == ".":
        visited[y][x] = H * W

  for y in range(1, H):  # ↓
    # 要素ごとの処理
    # print(visited)
    visited[y][:] = np.minimum(visited[y][:], visited[y - 1][:] + 1)
    # print(visited)
    # input()
    # print(visited[y])
    # exit(0)

  for y in range(H - 2, -1, -1):
    visited[y, :] = np.minimum(visited[y, :], visited[y + 1][:] + 1)

  for x in range(1, W):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x - 1] + 1)

  for x in range(W - 2, -1, -1):
    visited[:, x] = np.minimum(visited[:, x], visited[:, x + 1] + 1)

  # print(visited)
  # exit(0)

  # max_len = 0
  # for y in range(H):
  #   max_val = max(visited[y])
  #   max_len = max_len if max_len > max_val else max_val
  # print(max_len)
  print(np.max(visited))

if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=(combinations_count(x+y,x))
        print(ans%1000000007)

### FIXED CODE ###

import sys
import math
from operator import mul
from functools import reduce
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 
N = 10**6
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1] 

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

x,y= (int(_) for _ in input().split()) 
if (x+y)%3!=0:
    print(0)
    sys.exit()
else:
    n=(x+y)/3
    n=int(n)
    if x<n or y<n:
         print(0)
         sys.exit()
    else:
        x=x-n
        y=y-n
        ans=int(cmb(x+y, x,mod))
        print(ans%1000000007)
### BUGGY CODE ###


s = input()
n = len(s)
dp =[[0 for _ in range(13)] for _ in range(n+1)]
dp[0][0]=1


for i in range(n):
    if s[i]=="?":
        si = range(10)
    else:
        si = [int(s[i])]
    
    for sn in si:
        for j in range(13):
            dp[i+1][(10*j+sn)%13]+=dp[i][j]

print(dp[n][5]%(10**9+7))


### FIXED CODE ###


s = input()
n = len(s)
dp1 =[0 for _ in range(13)]
dp1[0]=1


move = [[] for _ in range(13)]

for i in range(10):
    for j in range(13):
        move[(10*j+i)%13].append(j)



for i in range(n):
    dp2 =[0 for _ in range(13)]
    if s[i]=="?":
        si = range(10)
        for mod,ex in enumerate(move):
            dp2[mod] += sum([dp1[x] for x in ex])
    else:
        si = int(s[i])
        for j in range(13):
            dp2[(10*j+si)%13]+=dp1[j]
    dp1 = [x%(10**9+7) for x in dp2] 


print(dp1[5])
### BUGGY CODE ###

x = int(input())
flg = 0
now_flg = 0
while flg == 0:
    mx  = int(x**0.5)
    for i in range(2, mx+1):
        if x % i == 0:
            now_flg = 1
            break
    fig = now_flg
    if flg == 0:
        x+=1
print(x)


### FIXED CODE ###

def com(_x):
    _flg = 1
    mx  = int(_x**0.5)
    for i in range(2, mx+1):
        if _x % i == 0:
            _flg = 0
            break
    return _flg


def main():
    x = int(input())
    flg = 0
    while flg == 0:
        #print("a")
        flg = com(x)
        if flg == 0:
            x+=1
    print(x)



if __name__ == "__main__":
    main()
### BUGGY CODE ###

def gcd(a, b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)


n = int(input())
a = list(map(int, input().split()))
ans = a[0]
for i in range(n):
    ans = gcd(i,ans)
for i in range(n):
    if i==0:
        t = a[1]
    else:
        t = a[0]
    for j in range(n):
        if j==i:
            continue
        t = gcd(a[j],t)
        if t<=ans:
            break
    ans = max(t,ans)
print(ans)


### FIXED CODE ###

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

n = int(input())
a = list(map(int, input().split()))
r = []
l = []
t = a[0]
for i in a:
    t = gcd(t, i)
    l.append(t)
t = a[-1]
for i in a[::-1]:
    t = gcd(t, i)
    r.append(t)
r = r[::-1]
ans = 0
for i in range(n):
    if i == 0:
        ans = max(ans, r[1])
        continue
    if i == n - 1:
        ans = max(ans, l[-2])
        continue
    ans = max(ans, gcd(l[i-1], r[i+1]))

print(ans)
### BUGGY CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf")]*n
dp[0] = 0

for i in range(1,n):
    for s in range(min(k,i)+1):
        dp[i] = min(dp[i],dp[i-s]+abs(h[i]-h[i-s]))

print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [float("inf")]*n
dp[0] = 0

for i in range(1,n):
    for s in range(1,min(k,i)+1):
        dp[i] = min(dp[i],dp[i-s]+abs(h[i]-h[i-s]))

print(dp[-1])
### BUGGY CODE ###

s=input()

cnt=0
while(True):
  if s.find("ABC") == -1:
    break
  else:
    cnt += s.count("ABC")
    s = s.replace("ABC","BCA")
    
print(cnt)

### FIXED CODE ###

s=input()

s2list=list(s.replace("BC","D"))
#print(s2list)

block_list=[]
bl=[]
for s2 in s2list:
  if s2=="A" or s2=="D":
    bl.append(s2)
  else:
    if len(bl)>0:
      block_list.append("".join(bl))
      bl=[]
else:
  if len(bl)>0:
    block_list.append("".join(bl))
#print(block_list)

answer=0
for bl in block_list:
  #print(bl)
  cnt_a=0
  for c in bl:
    if c=="A":
      cnt_a+=1
    else:
      answer+=cnt_a
    
print(answer)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort()
c.sort()
c = c[::-1]
answer = 0
for j in b:
	for k in range(n):
		if a[k] >= j:
			x = k
			break
		elif k == n-1:
			x = n
	for k2 in range(n):
		if c[k2] <= j:
			y = k2
			break
		elif k2 == n-1:
			y = n
	answer += x*y
print(answer)

### FIXED CODE ###

import bisect
n = int(input())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
a.sort()
c.sort()
answer = 0
for i in b:
	x = bisect.bisect_right(c,i)
	y = bisect.bisect_left(a,i)
	answer += (n-x)*y
print(answer)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
JK = list()
Ilist = [0]
for k in range(2, N):
    for j in range(1, k):
        if not S[j] == S[k]:
            JK.append((j, k))
            Ilist.append(j)

Iset = set(Ilist)
for jk in JK:
    j, k = jk
    for i in Iset:
        if not i < j:
            break
        if S[i] == S[j]:
            continue
        if S[i] == S[k]:
            continue
        if j-i == k-j:
            continue
        ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N):
    for j in range(i, N):
        k = 2*j - i
        if N > k and S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans -= 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from itertools import permutations
n = int(input())
strings = [input() for _ in range(n)]
dicts = []
sets = []
for i in strings:
    tmp_dict = defaultdict(lambda: 0)
    temp_set = set()
    for j in i:
        tmp_dict[j] += 1
        temp_set.add(j)
    dicts.append(tmp_dict)
    sets.append(temp_set)

intersection = sets[0]
for i in sets:
    intersection = intersection & i

final_dict = {}
for i in list(intersection):
    tmp = 100
    for j in dicts:
        t = j[i]
        if t < tmp:
            tmp = t
    final_dict[i] = tmp

final_words = ''
for f in final_dict.keys():
    final_words += final_dict[f]*f
words = [i for i in permutations(final_words)]
for i in words[0]:
    print(i, end='')

### FIXED CODE ###

from collections import defaultdict
n = int(input())
dicts = []
sets = []
da = dicts.append
for i in [input() for _ in range(n)]:
    tmp_dict = defaultdict(lambda: 0)
    for j in i:
        tmp_dict[j] += 1
    da(tmp_dict)

intersection = set(dicts[0].keys())
for i in dicts[1:]:
    intersection = intersection & i.keys()
final_words = ''
for i in sorted(list(intersection)):
    tmp = 100
    for j in dicts:
        t = j[i]
        if t < tmp:
            tmp = t
    final_words += i*tmp
print(final_words)
### BUGGY CODE ###

N, M= (int(i) for i in input().split())
A = [int(i) for i in input().split()]
BC = [list(map(int, input().split())) for _ in range(M)]
count = 0

BC = sorted(BC, key=lambda x: x[1],reverse=True)
min_A = min(A)

A.sort()

for B,C in BC:
  if min_A >= C and count > N:
    break
  else:
    l = min(B, N-count)
    for i in range(l):
      count+=1
      A.append(C)
      A.pop(A.index(min(A)))

ans = sum(A)

print(ans)


### FIXED CODE ###

N, M= (int(i) for i in input().split())
A = [int(i) for i in input().split()]
BC = [list(map(int, input().split())) for _ in range(M)]
count = 0

BC = sorted(BC, key=lambda x: x[1],reverse=True)
min_A = min(A)

for B,C in BC:
  if min_A >= C and count > N:
    break
  else:
    l = min(B, N-count)
    for i in range(l):
      count+=1
      A.append(C)

A.sort()

ans = sum(A[count:len(A)])

print(ans)
### BUGGY CODE ###

import math
K=int(input())
sum=0

for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            sum=sum+math.gcd(math.gcd(a,b),c)
print(sum)


### FIXED CODE ###

import math
K=int(input())
sum=0

for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            sum=sum+math.gcd(math.gcd(a,b),c)
print(sum)
### BUGGY CODE ###

#各桁の和を求める
def findSumOfDigits(n):
  sum = 0
  while n > 0:
    sum += int(n % 10)
    n = int(n / 10)
  return sum

N = int(input())

total = 0
for A in range(1,N + 1):
  for B in range(1,N + 1):
    if A + B == N:
      rec_A = findSumOfDigits(A)
      rec_B = findSumOfDigits(B)
      rec = rec_A + rec_B
      if total == 0:
        total = rec
      elif total >= rec:
        total = rec
        
print(total)

### FIXED CODE ###

#各桁の和を求める
def findSumOfDigits(n):
  sum = 0
  while n > 0:
    sum += int(n % 10)
    n = int(n / 10)
  return sum

N = int(input())

if N % 10 != 0 :
  print(findSumOfDigits(N))
else:
  print("10")
### BUGGY CODE ###

import itertools

n,m,q=map(int,input().split())

lis=[]
for i in range(q):
    lis.append(list(map(int,input().split())))

M=0
for l in map(list,itertools.combinations(range(1,n+m),n)):
    s=0
    for j in range(q):
        aj=lis[j][0]
        bj=lis[j][1]
        cj=lis[j][2]
        dj=lis[j][3]
        if (l[bj-1]-(bj-1))-(l[aj-1]-(aj-1))==cj:
            s+=dj
    M=max(M,s)
print(M)

### FIXED CODE ###

import itertools

n,m,q=map(int,input().split())

lis=[]
for i in range(q):
    lis.append(list(map(int,input().split())))

M=0
for l in map(list,itertools.combinations(range(1,n+m),n)):
    s=0
    for j in range(q):
        aj=lis[j][0]
        bj=lis[j][1]
        cj=lis[j][2]
        dj=lis[j][3]
        if l[bj-1]-bj-l[aj-1]+aj==cj:
            s+=dj
    M=max(M,s)
print(M)
### BUGGY CODE ###

N=int(input())
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
ans//=2
was=set()
for i in range(N):
    if ans<0:break
    for j in range(i+1,N):
        if ans<0:break
        for k in range(j+1,N):
            a,b,c=dist[i][j],dist[i][k],dist[j][k]
            if b<a and c<a:
                M=a
                S=b+c
                check=(i,j)
            elif a<b and c<b:
                M=b
                S=a+c
                check=(i,k)
            elif a<c and b<c:
                M=c
                S=a+b
                check=(j,k)
            else:continue
            if S==M:
                if check in was:continue
                ans-=M
                was|={check,}
            elif S<M:
                ans=-1*float('inf')
                break
if ans<0:ans=-1
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
N=int(input())
dist=[list(map(int,input().split())) for i in range(N)]
ans=sum([sum(dist[i]) for i in range(N)])
for i in range(N):
    dist[i][i]=float('inf')
ans//=2
def main(ans):
    for i in range(N):
        for j in range(i+1,N):
            Min=min(map(sum,zip(dist[i],dist[j])))
            if Min<dist[i][j]:
                return -1
            if Min==dist[i][j]:
                ans-=dist[i][j] 
    return ans
print(main(ans))
### BUGGY CODE ###

N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]
count =0
for i in range(N):
    count = A.count(i+1)
    if K-(Q-count) >0:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

from collections import Counter
N,K,Q=map(int,input().split())
A=[int(input()) for i in range(Q)]
C = Counter(A)
for i in range(N):
    count = C[i+1]
    if K-(Q-count) >0:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

#!/usr/bin/env python3
S = input().strip()
N = len(S)

# print([(i, j) for i in range(N) for j in range(i + 1, N + 1) if True or int(S[i:j]) % 2019 == 0])
print(sum([1 for i in range(N) for j in range(i + 1, N + 1) if int(S[i:j]) % 2019 == 0]))


### FIXED CODE ###

#!/usr/bin/env python3


def main():
    S = input()
    N = len(S)

    mod_count = [0] * 2019
    mod_count[0] = 1
    ssum = 0
    for i, c in enumerate(S[::-1]):
        ssum = (ssum + int(c) * pow(10, i, 2019)) % 2019
        mod_count[ssum] += 1

    print(sum([m * (m - 1) for m in mod_count]) // 2)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = input()
Slist = [S[i] for i in range(len(S))]
Q = int(input())
Query = [list(input().split()) for i in range(Q)]
Qlen = len(Query)
cnt = 0
for i in range(Qlen):
    if int(Query[i][0]) == 1:
        cnt +=1
    else:
        if int(Query[i][1]) == 1:
            if cnt % 2 != 0:   
                Slist = Slist + [Query[i][2]]
            else:
                Slist = [Query[i][2]] + Slist
        else:
            if cnt % 2 != 0:
                Slist = [Query[i][2]] + Slist
            else:
                Slist = Slist + [Query[i][2]]
if cnt % 2 == 0:
    print("".join(Slist))
else:
    Slist = Slist[::-1]
    print("".join(Slist))

### FIXED CODE ###

S = input()
Slist = [S[i] for i in range(len(S))]
Q = int(input())
Query = [list(input().split()) for i in range(Q)]
Qlen = len(Query)
reverse = False
back = []
head = []

for idx, value in enumerate(Query):
    if value[0] == "1":
        reverse ^= True
        head, back = back, head
    else:
        if value[1] == "1":
            head += [value[2]]
        else:
            back += [value[2]]

if reverse == False:
    head.reverse()
    print("".join(head + Slist + back))
else:
    head.reverse()
    print("".join(head + Slist[::-1] + back))
### BUGGY CODE ###

n = int(input())
def dividable(p):
    d_max = int(p**(1/2))
    yes=False
    if d_max*d_max==p:
        yes=True
    ret =0
    if yes:
        for i in range(1, d_max):
            if p % i == 0:
                ret += 1
        return ret*2+1
    else:
        for i in range(1, d_max+1):
            if p%i==0:
                ret+=1
        return ret*2
ls=[0]*(n+1)
for i in range(2, n+1):
    ls[i]= ls[i-1] + dividable(i-1)
print(ls[-1])

### FIXED CODE ###

n = int(input())

N_1 = n - 1
ans = 0
i = 1
j = 1
while i <= N_1:
    while j <= N_1:
        if i * j <=  N_1:
            ans += 1
        else:
            j = N_1
        j = j + 1
    j = 1
    i = i + 1

print(ans)
### BUGGY CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = sorted(A)
ans = [0 for i in range(aa[-1]+1)]
for i in aa:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2,aa[-1]+1,i):
      if j in aa:
	      ans[j] += 1
print(ans.count(1))

### FIXED CODE ###

import numpy as np
N = int(input())
A = list(map(int,input().split()))
aa = sorted(A)
ans = [0 for i in range(aa[-1]+1)]
for i in aa:
  ans[i] += 1
  if ans[i] == 1:
    for j in range(i*2,aa[-1]+1,i):
      ans[j] += 2
print(ans.count(1))
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
a = 0
S = 0
for i in range(N):
    for j in range(i+1,N):
        a = A[i]*A[j]
        aa = a%1000000007
        S += aa
p = S%1000000007
print(p)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
mod = 10**9+7
a,s = 0,0
for i in range(N):
    a += s*A[i]
    s += A[i]
    a %= mod
print(a)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
while len(A) > 0:
    count = 0
    for i in A:
        if i == A[0]:
            count += 1
        else:
            break
    if count >= A[0]:
        ans += count - A[0]
    else:
        ans += count
    A = A[count:]

print(ans)

### FIXED CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))
ans = 0
for num, count in collections.Counter(A).items():
    if num > count:
        ans += count
    elif num < count:
        ans += count - num

print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

ans = []
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ans.append(1)
    else:
        ans.append(0)

for i in lr:
    cnt = sum(ans[i[0]-1:i[1]-1])
    print(cnt)

### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

ans = [0] * n
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ans[i + 1] = ans[i] + 1
    else:
        ans[i + 1] = ans[i]

for i in lr:
    print(ans[i[1]-1]-ans[i[0]-1])
### BUGGY CODE ###

import sys
fin = sys.stdin.readline

import copy
ob = list(fin())
for i in range(len(ob)-1):
     if ob[i]=="0" and ob[i+1]=="1":
          ob[i]="1"
          ob[i+1]="0"
n = len(ob)
while True:
     ob_sub = copy.copy(ob)
     j=0
     for i in range(len(ob)-1):
          if ob[i]=="1" and ob[i+1]=="0":
               ob_sub[i],ob_sub[i+1] = "#","#"
               j+=2
     for i in range(j):
          ob_sub.remove("#")
     if ob_sub == ob:
          break
     else:
          ob = ob_sub
          
while True:
     ob_sub = copy.copy(ob)
     j=0
     for i in range(len(ob)-1):
          if ob[i]=="0" and ob[i+1]=="1":
               ob_sub[i],ob_sub[i+1] = "#","#"
               j+=2
     for i in range(j):
          ob_sub.remove("#")
     if ob_sub == ob:
          break
     else:
          ob = ob_sub

print(n-len(ob))

### FIXED CODE ###

import sys
fin = sys.stdin.readline
ob = list(fin())
print(min(ob.count("0"), ob.count("1"))*2)
### BUGGY CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	#b , c = tin()
	s = input()
	while True:
		p=''
		for i, c in enumerate(s):
			if p == 'S' and c == 'T':
				s = s[:i-1]+s[i+1:]
				#print(s)
				break
			p=c
		else:
			break
		
	return len(s)
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

### FIXED CODE ###

import sys

input_methods=['clipboard','file','key']
using_method=1
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(IN())
mod=1000000007

#+++++

def main():
	#a = int(input())
	#b , c = tin()
	s = list(input())[:-1]

	count_s = 0
	delete_num=0
	for c in s:
		if c == 'S':
			count_s+=1
		else: #if c == 'T':
			if count_s == 0:
				pass
			else:
				count_s-=1
				delete_num+=2
	return len(s)-delete_num
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)