# 108 學年度商業類學生技藝競賽
題目出處：[點擊](https://sci.me.ntnu.edu.tw/Contest/down?f_id=28183&c_Fileclass=2&ActionName=HistoryQuestionsList)

# pA. 統計答案得分

for _ in range(int(input())):
    a=list(input())
    ans=0
    temp=1
    for i in a:
        if i=='O':
            ans+=temp
            temp+=1
        else:
            temp=1
    print(ans)

# pB. 保齡球計分

arr = input().replace(" ", "")
ans = 0
idx = 0
for _ in range(10):
    if arr[idx] == 'X':  # 全倒
        next_two_rolls_score = 10
        if arr[idx + 1] == 'X':
            next_two_rolls_score += 10
            if arr[idx + 2] == 'X':
                next_two_rolls_score += 10
            else:
                next_two_rolls_score += int(arr[idx + 2])
        else:
            if arr[idx + 2] == '/':
                next_two_rolls_score += 10
            else:
                next_two_rolls_score += int(arr[idx + 1]) + int(arr[idx + 2])
        ans += 10 + next_two_rolls_score
        idx += 1
    elif arr[idx + 1] == '/':  # 補倒
        next_roll_score = 10 if arr[idx + 2] == 'X' else int(arr[idx + 2])
        ans += 10 + next_roll_score
        idx += 2
    else:
        ans += int(arr[idx]) + int(arr[idx + 1])
        idx += 2
print(ans)

# pC. 包含某個數

for _ in range(int(input())):
    ans=0
    a,b,n=map(int,input().split())
    for i in range(a,b+1):
        if str(n) in str(i):
            ans+=1
    print(ans)

# pD. 求餘數
\begin{cases}
1 & \text{if y = 0}\\\\
exp(x,y-1,m)\ast x\text{%}m & \text{if y&1}\\\\
exp(x,\tfrac{y}{2},m)\ast exp(x,\tfrac{y}{2},m)\text{%m} &\text{else}
\end{cases}

def exp(x,y,m):
    if y==0:return 1
    if y&1: return exp(x,y-1,m)*x%m
    t=exp(x,y//2,m)
    return t*t%m

for _ in range(int(input())):
    x,y,m=map(int,input().split())
    print(exp(x,y,m))

# pE. 出現的次數最多的DNA序列

for _ in range(int(input())):
    ans = ""
    r, c = map(int, input().split())
    arr = []
    for _ in range(r):
        arr.append(list(input()))
    dp = [[0]*(r) for _ in range(c)]
    for x in range(r):
        for y in range(c):
            dp[y][x] = arr[x][y]
    dna = ["A", "C", "G", "T"]
    for i in dp:
        temp = [0, 0, 0, 0]
        for j in range(4):
            temp[j] = i.count(dna[j])
        ans += dna[temp.index(max(temp))]
    print(ans)

# pF. 循環小數

for _ in range(int(input())):
    a, b = map(int, input().split())
    result = [f"{a//b}."]
    a = a % b * 10
    used = set()
    remain = []
    while a not in used:
        remain.append(a)
        used.add(a)
        a = a % b * 10
    i = 0
    while remain[i] != a:
        result.append("%d" % (remain[i] / b))
        i += 1
    result.append("(")
    j = i
    while i < len(remain) and i < 50:
        result.append("%d" % (remain[i] / b))
        i += 1
    if i < len(remain):
        result.append("...")
    result.append(")")
    print(''.join(result))

# pG. 著色問題

from collections import defaultdict
for _ in range(int(input())):
    v = int(input())
    d = defaultdict(list)
    for _ in range(int(input())):
        x, y = map(int, input().split())
        d[x].append(y)
        d[y].append(x)
    p = [0]*(v)
    vis = set()
    q = [0]
    head = 0
    flag = False
    while head < len(q):
        node = q[head]; head += 1
        for i in d[node]:
            if i not in vis:
                vis.add(i)
                q.append(i)
                p[i] = 0 if p[node] else 1
            else:
                if p[i] == p[node]:
                    print("F")
                    flag = True
                    break
        if flag:
            break
    else:
        print("T")  

# pH. 數字迷宮
經典DP
$$
dp(i,j)=min(dp(i-1,j),dp(i,j-1))+arr(i,j)
$$

for _ in range(int(input())):
    n=int(input())
    m=int(input())
    arr=[]
    for i in range(n):
        arr.append([int(i) for i in input().split()])
    dp=[[0]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if i==j==0:
                dp[i][j]=arr[i][j]
            elif i==0:
                dp[i][j]=dp[i][j-1]+arr[i][j]
            elif j==0:
                dp[i][j]=dp[i-1][j]+arr[i][j]
            else:
                dp[i][j]=min(dp[i-1][j],dp[i][j-1])+arr[i][j]
    print(dp[-1][-1])