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

import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
            break

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    a = AB[i][0]
    b = AB[i][1]

    ap = wantp(a)
    bp = wantp(b)


    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nCr(c[ap],2) + nCr(c[bp],2) - nCr(c[ap]+c[bp],2)

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

    ans.append(now)

ans.reverse()

for i in range(M):
    print (ans[i+1])


### FIXED CODE ###

import math

def nCr(n,r):

    if n-r >= 0:
        return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))
    else:
        return 0

def nC2(n):
    if n-2 >= 0:
        return (n*(n-1)) // 2
    else:
        return 0

def wantp(n): #Union-Find木の親の探索

    nown = n
    Q = []
    cnt = 0
    while True:

        if nown != p[nown]:
            Q.append(nown)
            nown = p[nown]

        else:
            for i in Q: #探索した途中にあるノードの親を根に変更
                p[i] = nown
                cnt += 1

            break

        cnt += 1

        if cnt > 10:
            print (n,nown,p[nown])

    return nown


N,M = map(int,input().split())

AB = []
for i in range(M):

    A,B = map(int,input().split())

    AB.append([A-1,B-1])

AB.reverse()


ans = []
ans.append(nCr(N,2))

p = [] #親
c = [] #子の数
rank = [1] * N #そのノードの子で構成された木の深さ

for i in range(N):

    p.append(i)
    c.append(1)

for i in range(M): #最後の橋から1本ずつ足していく

    #if i % 1000 == 0 or i > 25000:
        #print (i)

    #if i > 25000 : print ("A")

    a = AB[i][0]
    b = AB[i][1]

    #if i > 25000 : print ("B") 

    ap = wantp(a)
    bp = wantp(b)

    #if i > 25000 : print ("C")

    now = ans[-1]

    if ap != bp: #前回の答えから導出、Union-Find木の結合
        now = now + nC2(c[ap]) + nC2(c[bp]) - nC2(c[ap]+c[bp])

        #if i > 25000 : print ("D")

        if rank[ap] > rank[bp]:

            p[bp] = ap
            c[ap] += c[bp]

        elif rank[ap] < rank[bp]:

            p[ap] = bp
            c[bp] += c[ap]

        else:

            p[ap] = bp
            c[bp] += c[ap]

            rank[bp] += 1

        #if i > 25000 : print ("E")

    ans.append(now)
    #if i > 25000 : print ("F")
    #print (now,p)

#print ("test")
ans.reverse()

for i in range(M):
    print (ans[i+1])
### BUGGY CODE ###

import sys

N, X, Y = map(int, input().split())

d = [[sys.maxsize for _ in range(N)] for _ in range(N)]

for i in range(N):
  d[i][i] = 0
  if i == N-1:
    pass
  else:
    d[i][i+1] = 1
    d[i+1][i] = 1

d[X-1][Y-1] = 1
d[Y-1][X-1] = 1

for k in range(N):
  for i in range(N):
    for j in range(N):
      d[i][j] = min(d[i][j], d[i][k] + d[k][j])

answer = [0 for _ in range(N-1)]

for h in range(N):
  for i in range(N):
    if h != i:
      answer[d[h][i]-1] += 1

for k in range(N-1):
  print(answer[k]//2)

### FIXED CODE ###

import sys

N, X, Y = map(int, input().split())
X -= 1
Y -= 1

d = [[sys.maxsize for _ in range(N)] for _ in range(N)]

for i in range(N):
  for j in range(N):
    d[i][j] = min(abs(j-i), abs(X-i) + 1 + abs(j-Y), abs(Y-i) + 1 + abs(j-X))

answer = [0 for _ in range(N-1)]

for h in range(N):
  for i in range(h+1, N):
    if h != i:
      answer[d[h][i]-1] += 1

for k in range(N-1):
  print(answer[k])
### BUGGY CODE ###

N = int(input())
S = [''.join(sorted(input())) for _ in range(0, N)]
result = 0
for i, s in enumerate(S):
    for j in range(i + 1, len(S)):
        if s == S[j]:
            result += 1
print(result)

### FIXED CODE ###

N = int(input())
S = [''.join(sorted(input())) for _ in range(0, N)]
d = {}
result = 0
for s in S:
    if s in d.keys():
        result += d[s]
        d[s] += 1
    else:
        d[s] = 1
print(result)
### BUGGY CODE ###

def main():
    from collections import deque
    # import sys
    # input = sys.stdin.readline

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = [[-1] * (N + 1) for _ in range(N + 1)]  # 離席コスト,J字にコスト-1の区画を設ける
    for r in range((N + 1) // 2 + 1):
        dr = min(r, N - 1 - r)
        for c in range((N + 1) // 2 + 1):
            dc = min(c, N - 1 - c)
            H[r][c] = H[N - 1 - r][c] = H[N - 1 - r][N - 1 - c] = H[r][N - 1 - c] = min(dr, dc)
    S = [[1] * N for _ in range(N)]  # 着席

    ans = 0
    for pi in p:
        pi_r, pi_c = divmod(pi, N)

        hpi = H[pi_r][pi_c]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi_r][pi_c] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi_r, pi_c, hpi))
        while dq:
            r, c, h = dq.popleft()
            for nr, nc in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
                if H[nr][nc] > h:
                    H[nr][nc] = h
                    dq.append((nr, nc, h + S[nr][nc]))
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def build_cost_table(n):
    ret = [-1] * (n ** 2)
    for r in range(n):
        dr = min(r, n - 1 - r)
        for c in range(n):
            dc = min(c, n - 1 - c)
            ret[r * n + c] = min(dr, dc)
    return ret


def main():
    from collections import deque

    N = int(input())
    *p, = (int(x) - 1 for x in input().split())

    H = build_cost_table(N)  # 離席コスト
    S = [1] * (N ** 2)  # 着席

    ans = 0
    for pi in p:
        hpi = H[pi]  # piの離席コスト
        ans += hpi  # piの離席コストを加算
        S[pi] = 0  # piを空席にする

        # BFSで離席コストを更新
        dq = deque()
        dq.append((pi, hpi))
        while dq:
            x, h = dq.popleft()
            r, c = divmod(x, N)

            nx = x - N
            if r != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + N
            if r != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x - 1
            if c != 0 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

            nx = x + 1
            if c != N - 1 and H[nx] > h:
                H[nx] = h
                dq.append((nx, h + S[nx]))

    print(ans)


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

from collections import deque

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

adj_list = [[] for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj_list[a].append(b)
    adj_list[b].append(a)

distance = [-1] * n
prev = [-1] * n

q = deque()
q.append([0, 0, 0])  #[room, distance, prev]

while len(q) > 0:
    room, d, p = q.popleft()
    if distance[room] == -1:
        distance[room] = d
        prev[room] = p

    for n_room in adj_list[room]:
        if distance[n_room] > 0:
            continue
        q.append([n_room, d + 1, room])

flag = True
for i in range(n):
    if distance[i] < 0:
        flag = False
        break

if flag is True:
    print("Yes")
    for i in range(1, n):
        print(prev[i] + 1)
else:
    print("No")


### FIXED CODE ###

from collections import deque

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

adj_list = [[] for _ in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    adj_list[a].append(b)
    adj_list[b].append(a)

distance = [-1] * n
prev = [-1] * n

q = deque()
q.append([0, 0, 0])  #[room, distance, prev]

while len(q) > 0:
    room, d, p = q.popleft()
    #if distance[room] == -1:
    #    distance[room] = d
    #    prev[room] = p

    for n_room in adj_list[room]:
        if distance[n_room] > 0:
            continue
        q.append([n_room, d + 1, room])
        distance[n_room] = d + 1
        prev[n_room] = room

flag = True
for i in range(n):
    if distance[i] < 0:
        flag = False
        break

if flag is True:
    print("Yes")
    for i in range(1, n):
        print(prev[i] + 1)
else:
    print("No")
### BUGGY CODE ###

S = input()
text = S[::-1]
MOD = 10**9 + 7


def main():
    DP = [0] * 13
    if text[0] == '?':
        for i in range(10):
            DP[i] = 1
    else:
        DP[int(text[0])] = 1

    for i in range(1, len(S)):
        preDP = DP
        DP = [0] * 13
        if text[i] == '?':
            for x in range(10):
                nx = x * 10 ** i
                for k in range(13):
                    t = (nx + k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(text[i]) * 10 ** i
            for k in range(13):
                t = (y+k) % 13
                DP[t] = preDP[k] % MOD
    ans = DP[5]
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
MOD = 10**9 + 7


def main():
    S = input().rstrip()
    DP = [0] * 13
    n = len(S)
    DP[0] = 1

    for i in range(0, n):
        preDP = DP
        DP = [0] * 13
        if S[i] == '?':
            for k in range(13):
                for x in range(10):
                    t = (x + 10*k) % 13
                    DP[t] += preDP[k]
                    DP[t] %= MOD
        else:
            y = int(S[i])
            for k in range(13):
                t = (y+10*k) % 13
                DP[t] += preDP[k]
                DP[t] %= MOD

    ans = DP[5]
    print(ans)


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

S = int(input())
for i in range(1,int(S**0.5)+1):
    if(S%i==0):
        j = S//i
        if(j>=10**9):continue
        print(0,0,i,0,0,j)
        break


### FIXED CODE ###

S = int(input())
x3 = 10**9-S%(10**9)
x3 = 0 if x3 == 10**9 else x3
y3 = (S+x3)//(10**9)
print(0,0,10**9,1,x3,y3)
### BUGGY CODE ###

def main():
    N = int(input())
    a = list(map(int, input().split()))
    A = [0]*4
    for x in a:
        A[x] += 1

    dp = [[[0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(A[3]+1):
        for j in range(A[2]+A[3] + 1 - k):
            for i in range(A[1]+A[2]+A[3] + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = N
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)

    print(dp[A[1]][A[2]][A[3]])
main()


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))
    a = A.count(1)
    b = A.count(2)
    c = A.count(3)
    floatN = N*1.0
    dp = [[[.0]*(N+1) for i in range(N+1)] for j in range(N+1)]

    for k in range(c+1):
        for j in range(b+c + 1 - k):
            for i in range(N + 1 - k - j):
                if i + j+k == 0:
                    continue
                dp[i][j][k] = floatN
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * i
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * j
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * k
                dp[i][j][k] /= (i+j+k)
    print(dp[a][b][c])


main()
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import deque, defaultdict
def main():
    n, c, k = map(int, input().split())
    times = [int(input()) + k for _ in range(n)]
    times.sort()
    times = deque(times)

    r = 0
    for i1 in range(max(times) + 1):
        if times and i1 == times[0]:
            r += 1
            g = 0
            while g < c:
                if times and times[0] <= i1 + k:
                    times.popleft()
                    g += 1
                else:
                    break
    print(r)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
from math import floor
def main():
    n, c, k = map(int, input().split())
    times = defaultdict(int)
    for _ in range(n):
        times[int(input()) + k] += 1
    # ts:時間順に「時間ごとの出発したい人数」を並べたもの
    ts = dict(sorted(times.items()))

    r = 0
    busg = c # バスに乗せられる人数
    busstart = - k - 1
    for tse in ts:
        if busstart + k < tse: # 前のバスに間に合わない場合。バスを仕立てる
            r += floor(ts[tse] / c) # 満員になるバス台数を+する。
            nokori = ts[tse] % c
            if nokori: # 残りがいるならバスを仕立てる。
                r += 1
                busg = c - nokori
                busstart = tse
            else:
                busstart = -k - 1
        else:
            if busg >= ts[tse]: #バスに乗りきれる場合
                busg -= ts[tse]
            else:             # バスに乗り切れない場合。バスを仕立てる。
                r += floor(ts[tse] / c)
                nokori = ts[tse] % c
                if nokori:
                    r += 1
                    busg = c - nokori
                    busstart = tse
                else:
                    busstart = -k - 1
    print(r)

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

n, m = map(int, input().split())
l = [int(input())-1 for _ in range(m)]
res = [0, 1]

for i in range(n):
  if i in l:
    res[0] = res[1]
    res[1] = 0
  else:
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
    
print(res[1])

### FIXED CODE ###

n, m = map(int, input().split())
l = [int(input())-1 for _ in range(m)]
res = [0, 1]
skip = 0

if m != 0:
  for i in range(n):
    if i == l[skip]:
      res[0] = res[1]
      res[1] = 0
      if skip < m-1:
        skip += 1
    else:
      tmp = res[1]
      res[1] += res[0]
      res[0] = tmp
      res[1] %= 10**9 + 7
      res[0] %= 10**9 + 7
else:
  for i in range(n):
    tmp = res[1]
    res[1] += res[0]
    res[0] = tmp
    res[1] %= 10**9 + 7
    res[0] %= 10**9 + 7
      
print(res[1])
### BUGGY CODE ###

N = int(raw_input())

upper = list()
lower = list()

right_end = 0
search_end = 0 
while True:
    if right_end == 0:
        for q in [['.', '.'], ['.', '#'], ['#', '.'], ['#', '#']]:
            print "".join(upper + [q[0]])
            print "".join(lower + [q[1]])

            r = raw_input()
            if r == 'T':
                upper.append(q[0])
                lower.append(q[1])
                break
            elif r == 'end':
                search_end = 1
                break
            if r == 'F' and q == ['#', '#']:
                right_end = 1
    else:
        for q in [['.', '.'], ['.', '#'], ['#', '.'], ['#', '#']]:
            print "".join([q[0]] + upper)
            print "".join([q[1]] + lower)
            
            r = raw_input()
            if r == 'T':
                upper.insert(0,q[0])
                lower.insert(0,q[1])
                break
            elif r == 'end':
                search_end = 1
                break
    if search_end == 1:
        break




### FIXED CODE ###

import sys
N = int(raw_input())
upper = list()
lower = list()

right_end = 0
search_end = 0 
while True:
    if right_end == 0:
        for q in [['.', '.'], ['.', '#'], ['#', '.'], ['#', '#']]:
            print "".join(upper + [q[0]])
            print "".join(lower + [q[1]])
            sys.stdout.flush()

            r = raw_input()
            if r == 'T':
                upper.append(q[0])
                lower.append(q[1])
                break
            elif r == 'end':
                search_end = 1
                break
            if r == 'F' and q == ['#', '#']:
                right_end = 1
    else:
        for q in [['.', '.'], ['.', '#'], ['#', '.'], ['#', '#']]:
            print "".join([q[0]] + upper)
            print "".join([q[1]] + lower)
            sys.stdout.flush()
            
            r = raw_input()
            if r == 'T':
                upper.insert(0,q[0])
                lower.insert(0,q[1])
                break
            elif r == 'end':
                search_end = 1
                break
    if search_end == 1:
        break
### BUGGY CODE ###

n=int(input())
list1=list(map(int ,input().split()))
list2=[]
for i in range(n):
  for j in range(i+1,n):
    list2.append(list1[i]*list1[j])
a=sum(list2)%1000000007
    
print(a)

### FIXED CODE ###

n=int(input())
ans=0
mod=10**9+7
list1=list(map(int ,input().split()))
sums=sum(list1)

for i in list1:
  sums -=i
  ans +=sums*i%mod
  
print(ans%mod)
### BUGGY CODE ###

def main():
    N, P = map(int, input().split())
    S = map(int, input())

    dp = [[0] * P for _ in range(N + 1)]

    for i, x in enumerate(S):
        dp[i + 1][x % P] += 1
        for rest in range(P - 1, -1, -1):
            # dp[i + 1][rest] += dp[i][rest]

            next_rest = (rest * 10 + x) % P
            dp[i + 1][next_rest] += dp[i][rest]

    ret = sum(dp[i][0] for i in range(1, N + 1))
    print(ret)


if __name__ == '__main__':
    main()

# import sys
#
# sys.setrecursionlimit(10 ** 7)
#
# input = sys.stdin.readline
# rstrip()
# int(input())
# map(int, input().split())


### FIXED CODE ###

def main():
    N, P = map(int, input().split())
    S = [int(c) for c in input()]

    ret = 0
    if P in {2, 5}:
        for i, x in enumerate(S, 1):
            if x % P == 0:
                ret += i
        print(ret)
        return

    else:
        curr_num = 0
        counter = [0] * P
        counter[0] = 1
        for i, x in enumerate(reversed(S)):
            curr_num = (curr_num + x * pow(10, i, P)) % P
            ret += counter[curr_num]
            counter[curr_num] += 1
        print(ret)
        return


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

"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""

from __future__ import division
from sys import stdin, maxint

def lcs(s1, s2):
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in xrange(1, la + 1):
		dp2 = dp1[0:]
		for j in xrange(1, lb + 1):
			if s1[i - 1] == s2[j - 1]:
				dp1[j] = dp2[j - 1] + 1
			else:
				dp1[j] = max(dp1[j - 1], dp2[j])

	return dp1[-1]

if __name__ == '__main__':
	tc = int(stdin.readline())
	for _ in range(tc):
		sa = stdin.readline().strip()
		sb = stdin.readline().strip()
		print(lcs(sa, sb))

### FIXED CODE ###

"""
problem statment url: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_10_C
"""


def lcs():
	s1 = raw_input()
	s2 = raw_input()
	la, lb = len(s1), len(s2)
	dp1 = [0 for _ in range(lb + 1)]

	for i in range(la):
		dp2 = dp1 + []
		for j in range(lb):
			if s1[i] == s2[j]:
				dp1[j + 1] = dp2[j] + 1
			elif dp1[j + 1] < dp1[j]:
				dp1[j + 1] = dp1[j]

	return dp1[-1]

if __name__ == '__main__':
	tc = int(raw_input())
	for _ in range(tc):
		print(lcs())
### BUGGY CODE ###

def slove():
    import sys
    import collections
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = list(map(int, input().rstrip('\n').split()))
    l.sort()
    cnt = 0
    d = collections.defaultdict(int)
    for i in range(1, n - 1):
        for j in range(i + 1, n):
            a, b = [l[i], l[j]]
            tl = [a + b, abs(a - b)]
            mi = min(tl) + 1
            ma = min(max(tl) - 1, a - 1)
            for k in range(i-1, -1, -1):
                if l[k] < mi:
                    break
                elif mi <= l[k] <= ma:
                    ttl = sorted([i, j, k])
                    if (ttl[0], ttl[1], ttl[2]) not in d:
                        d[(ttl[0], ttl[1], ttl[2])]
                        cnt += 1
    print(cnt)


if __name__ == '__main__':
    slove()


### FIXED CODE ###

def slove():
    import sys
    import collections
    import bisect
    input = sys.stdin.readline
    n = int(input().rstrip('\n'))
    l = list(map(int, input().rstrip('\n').split()))
    l.sort()
    cnt = 0
    d = collections.defaultdict(int)
    for i in range(n-2):
        for j in range(i+1, n-1):
            ma = l[i] + l[j]
            p = bisect.bisect_left(l, ma)
            if j < p:
                cnt += p - j - 1
    print(cnt)


if __name__ == '__main__':
    slove()
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)

indegree = [0] * n_game
for i in range(n_game):
    for v in edge[i]:
        indegree[v] += 1

ans = 0
cand = [i for i in range(n_game) if indegree[i] == 0]
ts = []
while cand:
    ts.extend(cand)
    cand2 = []
    for ci in cand:
        for v in edge[ci]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand2.append(v)
    cand = cand2
    ans += 1

if len(ts) != n_game:
    ans = -1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = [list(map(lambda x: int(x)-1, input().split())) for _ in range(n)]

def calc_idx(x, y):
    if x > y:
        x, y = y, x
    return x + y*(y-1)//2

n_game = n * (n-1) // 2
edge = [[] for i in range(n_game)]
for i in range(n):
    for j in range(1, n-1):
        g1 = calc_idx(i, a[i][j-1])
        g2 = calc_idx(i, a[i][j])
        edge[g1].append(g2)

indegree = [0] * n_game
for i in range(n_game):
    for v in edge[i]:
        indegree[v] += 1

ans = 0
cand = [i for i in range(n_game) if indegree[i] == 0]
ts = []
while cand:
    ts.extend(cand)
    cand2 = []
    for ci in cand:
        for v in edge[ci]:
            indegree[v] -= 1
            if indegree[v] == 0:
                cand2.append(v)
    cand = cand2
    ans += 1

if len(ts) != n_game:
    ans = -1

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

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n - 1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

from heapq import heappop, heappush

def main():
    cost = dict()
    for a, b, c in abc:
        if a-1 in cost:
            cost[a-1] = cost[a-1] + [(b-1, c)]
        else:
            cost[a-1] = [(b-1, c)]
        if b-1 in cost:
            cost[b-1] = cost[b-1] + [(a-1, c)]
        else:
            cost[b-1] = [(a-1, c)]

    start = K - 1
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        for v, weight in cost.get(u, []):
            alt = du + weight
            if d[v] > alt:
                d[v] = alt
                heappush(q, (alt, v))

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()


### FIXED CODE ###

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n - 1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

from heapq import heappop, heappush

def main():
    cost = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    # print(cost)

    start = K - 1
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        for v, weight in cost[u]:
            alt = du + weight
            if d[v] > alt:
                d[v] = alt
                heappush(q, (alt, v))

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

if __name__ == '__main__':
    main()