CodeEff/ECCO huggingface dataset:
# Original solution
import functools


N, MOD = int(eval(input())), 10 ** 9 + 7


def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True


@functools.lru_cache(maxsize=None)
def dfs(cur, last3):
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    return ret


print((dfs(0, 'TTT')))


# Optimized solution
import functools


N, MOD = int(eval(input())), 10 ** 9 + 7


@functools.lru_cache(maxsize=None)
def ok(last4):
    for i in range(4):
        t = list(last4)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1]
        if ''.join(t).count('AGC') >= 1:
            return False
    return True


@functools.lru_cache(maxsize=None)
def dfs(cur, last3):
    if cur == N:
        return 1
    ret = 0
    for c in 'ACGT':
        if ok(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % MOD
    return ret


print((dfs(0, 'TTT')))
# Original solution
import collections, itertools
N = int(eval(input()))
mod = 10**9 + 7
cd = collections.defaultdict
dp = cd(lambda: cd(lambda: cd(lambda: cd(int))))
dp[0][3][3][3] = 1
count = 0
for i in range(N):
    for c0, c1, c2, c3 in itertools.product(list(range(4)), repeat=4):
        A1 = [c1, c2, c3]
        A2 = [c0, c2, c3]
        A3 = [c0, c1, c3]
        if A1 in [[0, 1, 2], [1, 0, 2], [0, 2, 1]] or [0, 1, 2] in [A2, A3]:
            continue
        dp[i + 1][c1][c2][c3] += dp[i][c0][c1][c2]
        dp[i + 1][c1][c2][c3] %= mod
        if i == N - 1:
            count += dp[i][c0][c1][c2]
            count %= mod
print(count)
# https://www.youtube.com/watch?v=w2AEXSloYk8


# Optimized solution
import collections, itertools
N = int(eval(input()))
mod = 10**9 + 7
# cd = collections.defaultdict
# dp = cd(lambda: cd(lambda: cd(lambda: cd(int))))
dp = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)]
      for _ in range(N + 1)]
dp[0][3][3][3] = 1
count = 0
for i in range(N):
    for c0, c1, c2, c3 in itertools.product(list(range(4)), repeat=4):
        A1 = [c1, c2, c3]
        A2 = [c0, c2, c3]
        A3 = [c0, c1, c3]
        if A1 in [[0, 1, 2], [1, 0, 2], [0, 2, 1]] or [0, 1, 2] in [A2, A3]:
            continue
        dp[i + 1][c1][c2][c3] += dp[i][c0][c1][c2]
        dp[i + 1][c1][c2][c3] %= mod
        if i == N - 1:
            count += dp[i][c0][c1][c2]
            count %= mod
print(count)
# https://www.youtube.com/watch?v=w2AEXSloYk8
# Original solution
import collections, itertools
N = int(eval(input()))
mod = 10**9 + 7
dp = collections.defaultdict(int)
dp['TTTA'] = dp['TTTG'] = dp['TTTC'] = dp['TTTT'] = 1
for _ in range(N - 1):
    dp2 = collections.defaultdict(int)
    for p, q, r, s, t in itertools.product('AGCT', repeat=5):
        if 'AGC' in [q + s + t, s + r + t, r + s + t, q + r + t, r + t + s]:
            continue
        else:
            dp2[q + r + s + t] += dp[p + q + r + s] % mod
    dp = dp2
print((sum(dp.values()) % mod))


# Optimized solution
import collections, itertools
N = int(eval(input()))
mod = 10**9 + 7
dp = collections.defaultdict(int)
dp['TTTA'] = dp['TTTG'] = dp['TTTC'] = dp['TTTT'] = 1
for _ in range(N - 1):
    dp2 = collections.defaultdict(int)
    for p, q, r, s, t in itertools.product('AGCT', repeat=5):
        if 'AGC' in [q + s + t, s + r + t, r + s + t, q + r + t, r + t + s]:
            continue
        else:
            dp2[q + r + s + t] += dp[p + q + r + s]
    dp = dp2
print((sum(dp.values()) % mod))
# Original solution
from itertools import product
from copy import deepcopy

n = int(eval(input()))
mod = 10 ** 9 + 7

comp = {"A": 0, "C": 1, "G": 2, "T": 3}

dp = [[0] * (4 ** 3) for _ in range(n + 1)]

bad = [0b001001, 0b000110, 0b100001]
for i in range(4 ** 3):
    if not i in bad:
        dp[3][i] = 1


def is_ok(li):
    for i in range(4):
        tmp = deepcopy(li)
        if i >= 1:
            tmp[i-1], tmp[i] = tmp[i], tmp[i-1]

        if "".join(tmp).count("AGC") >= 1:
            return False

    return True


def comp2int(li):
    ret = 0
    for i, e in enumerate(li):
        ret += comp[e] << 2 * (2 - i)

    return ret


for i in range(3, n):
    for j in product(list(comp.keys()), repeat=3):
        for k in list(comp.keys()):
            last4 = list(j) + [k]
            if is_ok(last4):
                j_prev = comp2int(j)
                j_nxt = comp2int(last4[1:])
                dp[i+1][j_nxt] += dp[i][j_prev]
                dp[i+1][j_nxt] %= mod

ans = 0
for i in range(4 ** 3):
    ans += dp[n][i]
    ans %= mod

print(ans)


# Optimized solution
from itertools import product
from copy import deepcopy

n = int(eval(input()))
mod = 10 ** 9 + 7

comp = {"A": 0, "C": 1, "G": 2, "T": 3}
keys = list(comp.keys())

dp = [[0] * (4 ** 3) for _ in range(n + 1)]

bad = [0b001001, 0b000110, 0b100001]
for i in range(4 ** 3):
    if not i in bad:
        dp[3][i] = 1


def is_ok(li):
    for i in range(4):
        tmp = deepcopy(li)
        if i >= 1:
            tmp[i-1], tmp[i] = tmp[i], tmp[i-1]

        if "".join(tmp).count("AGC") >= 1:
            return False

    return True


def comp2int(li):
    ret = 0
    for i, e in enumerate(li):
        ret += comp[e] << 2 * (2 - i)

    return ret


for i in range(3, n):
    for last4 in product(keys, repeat=4):
        last4 = list(last4)
        if is_ok(last4):
            j_prev = comp2int(last4[:-1])
            j_nxt = comp2int(last4[1:])
            dp[i+1][j_nxt] += dp[i][j_prev]
            dp[i+1][j_nxt] %= mod

ans = 0
for i in range(4 ** 3):
    ans += dp[n][i]
    ans %= mod

print(ans)
# Original solution
from itertools import product
from collections import defaultdict
MOD = 10**9 + 7
N = int(eval(input()))
# XAGC, XGAC, AXGC, AGXC, XACG: prohibited
A=0; C=1; G=2; T=3
cur = defaultdict(lambda: 1)
cur[(A,G,C)] = cur[(G,A,C)] = cur[(A,C,G)] = 0
for _ in range(3,N):
    prev = cur
    cur = defaultdict(int)
    for (i,j,k,l) in product(list(range(4)),repeat=4):
        if ((j,k,l)==(A,G,C) or (j,k,l)==(G,A,C) or (i,k,l)==(A,G,C) or
            (i,j,l)==(A,G,C) or (j,k,l)==(A,C,G)):
            continue
        else:
            cur[(j,k,l)] += prev[(i,j,k)]
    for ijk in product(list(range(4)),repeat=3):
        cur[ijk] %= MOD

ans = sum(cur.values()) % MOD
if N <= 3:
    print(([1,4,16,61][N]))
else:
    print(ans)

# Optimized solution
from itertools import product
from collections import defaultdict
MOD = 10**9 + 7
N = int(eval(input()))
D, L = 4, 3
AGC = list(range(L))
ATGC = list(range(D))
cur = defaultdict(lambda: 1)
# XAGC, XGAC, AXGC, AGXC, XACG: prohibited
flip = lambda x, n: x[:n] + [x[n+1],x[n]] + x[n+2:]
prohibited1 = [tuple(AGC)] + [tuple(flip(AGC,i)) for i in range(L-1)]
prohibited2 = ({(X,) + p for p in prohibited1 for X in ATGC} | 
             {tuple(flip([X]+AGC,0)) for X in ATGC} |
             {tuple(flip(AGC+[X],L-1)) for X in ATGC})
for p in prohibited1:
    cur[p] = 0
for _ in range(L,N):
    prev = cur
    cur = defaultdict(int)
    for recent in product(ATGC, repeat=L+1):
        if recent in prohibited2:
            continue
        else:
            cur[recent[1:]] += prev[recent[:-1]]
    for latest in product(ATGC, repeat=L):
        cur[latest] %= MOD

ans = sum(cur.values()) % MOD
if N < L:
    print((D**N))
elif N == L:
    print((D**L - len(prohibited1)))
else:
    print(ans)
# Original solution
def main():
    atgc = ["A", "T", "G", "C"]
    mod = 10 ** 9 + 7
    n = int(eval(input()))

    dp = [[[[0 for i3 in range(4)] for i2 in range(4)] for i1 in range(4)] for i0 in range(n)]

    for i in range(4):
        for j in range(4):
            for k in range(4):
                dp[0][i][j][k] = 1
    dp[0][0][2][3] = 0
    dp[0][0][3][2] = 0
    dp[0][2][0][3] = 0

    for t in range(n-3):
        for i in range(4):
            for j in range(4):
                for k in range(4):
                    dp[t+1][i][j][k] = dp[t][0][i][j] + dp[t][1][i][j] + dp[t][2][i][j] + dp[t][3][i][j]

        for i in range(4):
            dp[t+1][i][2][3] -= dp[t][0][i][2]
        for i in range(4):
            dp[t+1][2][i][3] -= dp[t][0][2][i]
        #AGG→GGC
        dp[t + 1][2][2][3] += dp[t][0][2][2]


        dp[t+1][0][2][3] = 0
        dp[t+1][0][3][2] = 0
        dp[t+1][2][0][3] = 0

    ans = 0
    for i in range(4):
        for j in range(4):
            for k in range(4):
                ans += dp[n-3][i][j][k]
    print((ans%mod))
main()



# Optimized solution
import itertools

def main():
    atgc = ["A", "T", "G", "C"]
    mod = 10 ** 9 + 7
    n = int(eval(input()))

    dp = [[[[0 for i3 in range(4)] for i2 in range(4)] for i1 in range(4)] for i0 in range(n)]

    for i, j, k in itertools.product(list(range(4)), list(range(4)), list(range(4))):
        dp[0][i][j][k] = 1
    dp[0][0][2][3] = 0 #AGC
    dp[0][0][3][2] = 0 #ACG
    dp[0][2][0][3] = 0 #GAC

    for t in range(n-3):
        for i, j, k in itertools.product(list(range(4)), list(range(4)), list(range(4))):
            dp[t+1][i][j][k] = dp[t][0][i][j] + dp[t][1][i][j] + dp[t][2][i][j] + dp[t][3][i][j]

        for i in range(4):
            dp[t+1][i][2][3] -= dp[t][0][i][2] #(A)*GC
        for i in range(4):
            dp[t+1][2][i][3] -= dp[t][0][2][i] #(A)G*C
        #(A)GGCが重複しているので
        dp[t+1][2][2][3] += dp[t][0][2][2]

        dp[t+1][0][2][3] = 0 #AGC
        dp[t+1][0][3][2] = 0 #ACG
        dp[t+1][2][0][3] = 0 #GAC

    ans = 0
    for i, j, k in itertools.product(list(range(4)), list(range(4)), list(range(4))):
        ans += dp[n-3][i][j][k]
    print((ans%mod))
main()
# Original solution
n = int(eval(input()))
ans = 0
hoges = []
seeds = 'ATCG'
def ng(currents):
  v = 'AGC' in currents
  # for k in range(max(1, 0), len(currents)):
  for k in range(max(1, len(currents) - 3), len(currents)):
    v = v or 'AGC' in (currents[:k-1] + currents[k] + currents[k-1] + currents[k+1:])
  return v
memo = {}
ng_memo = {} # 後ろ4つだけ見ればNGわかる？
def f(index, currents):
  ng_key = currents[-4:]
  key = '%d:%s' % (index, currents[-4:])
  # print(key)
  if ng_key in ng_memo:
    return 0
  if key in memo:
    return memo[key]
  if ng(currents):
    ng_memo[key] = True
    return 0
  if index == n:
    return 1
  memo[key] = sum([f(index+1, currents + s) for s in seeds])
  return memo[key]

print((f(0, '') % int(1e9+7)))

# 3:      61
# 4:     230
# 5:     865
# 6:    3247
# 7:   12185
# 8:   45719


# Optimized solution
n = int(eval(input()))
seeds = 'ATCG'
def ng(currents):
  v = 'AGC' in currents
  for k in range(max(1, len(currents) - 3), len(currents)):  # 先頭の方はチェック済み
    v = v or 'AGC' in (currents[:k-1] + currents[k] + currents[k-1] + currents[k+1:])
  return v

memo = {}  # 今の長さと最新4つだけメモする
def f(index, currents):
  key = '%d:%s' % (index, currents[-4:])
  if key not in memo:
    if ng(currents):
      memo[key] = 0
    else:
      memo[key] = 1 if index == n else sum([f(index+1, currents + s) for s in seeds])
  return memo[key]

print((f(0, '') % int(1e9+7)))
# Original solution
Mod = 10**9+7
p = ["XAGC", "XGAC", "XACG"] + ["AGCX", "GACX", "ACGX"] + ["AGXC", "AXGC"]
q = ["A", "G", "C", "T"]
f = []
for s in p:
  for c in q:
    f.append(s.replace("X",c))

r = ["AGC", "GAC", "ACG"]

d = {}
e = {}
for x in q:
  for y in q:
    for z in q:
      s = x+y+z
      if not s in r:
        d[s] = 1
        e[s] = 0
      
n = int(eval(input()))
for i in range(n-3):
  for s in list(e.keys()):
    for c in q:
      t = s+c
      if t in f:
        continue
      e[t[1:]] = (e[t[1:]]+d[s])%Mod
  for s in list(e.keys()):
    d[s] = e[s]
    e[s] = 0
    
print((sum(d.values())%Mod))

# Optimized solution
Mod = 10**9+7
f3 = ["AGC", "GAC", "ACG"]
f4 = ["AGAC","AGGC","AGCC","AGTC"] + ["AAGC","AGGC","ACGC","ATGC"]
q = ["A", "G", "C", "T"]

d = {}
e = {}
for x in q:
  for y in q:
    for z in q:
      s = x+y+z
      if not s in f3:
        d[s] = 1
        e[s] = 0
      
n = int(eval(input()))
for i in range(n-3):
  for s in list(e.keys()):
    for c in q:
      t = s+c
      if t[1:] in f3 or t in f4:
        continue
      e[t[1:]] = (e[t[1:]]+d[s])%Mod
  for s in list(e.keys()):
    d[s] = e[s]
    e[s] = 0
    
print((sum(d.values())%Mod))
# Original solution
N = int(input().strip())
M = pow(10, 9) + 7
a = 1
g = 1
ag = 0
agg = 0
agt = 0
atg = 0
ac = 0
at = 0
aa = 0
ga = 0

al = 4
nal = 0

for i in range(N-1):
    nal = (al * 4) % M
    nal = (nal + M - (ag + ac + ga + agg + agt + atg) ) % M

    agg = ag
    agt = ag
    atg = at
    ag = a
    aa = a
    at = a
    nac = (a + M- ga) % M
    ga = g
    a = al
    g = (al + M - ac) % M
    ac = nac
    al = nal
print(al)


# Optimized solution
a,g,a_,a__,ac,ga,al=[0]*6+[1]
for i in range(int(eval(input()))):
    a__,a_,ac,ga,a,g,al=a_,a,a-ga,g,al,al-ac,(al*4-(a_+ac+ga+a__*3))%(pow(10,9)+7)
print(al)
# Original solution
n, mod = int(eval(input())), 10 ** 9 + 7
memo = [{} for i in range(n+1)]
def check(l):
    for i in range(4):
        t = list(l)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1] # 順序の入れ替え
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for c in 'ACGT':
        if check(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
    memo[cur][last3] = ret
    return ret

print((dfs(0, 'TTT')))


# Optimized solution
"""
n, mod = int(input()), 10 ** 9 + 7
memo = [{} for i in range(n+1)]
def check(l):
    for i in range(4):
        t = list(l)
        if i >= 1:
            t[i-1], t[i] = t[i], t[i-1] # 順序の入れ替え
        if ''.join(t).count('AGC') >= 1:
            return False
    return True

def dfs(cur, last3):
    if last3 in memo[cur]:
        return memo[cur][last3]
    if cur == n:
        return 1
    ret = 0
    for c in 'ACGT':
        if check(last3 + c):
            ret = (ret + dfs(cur + 1, last3[1:] + c)) % mod
    memo[cur][last3] = ret
    print(cur, memo)
    return ret

print(dfs(0, 'TTT'))
"""

n, mod = int(eval(input())), 10 ** 9 + 7
memo = [[[[0 for _ in range(4)] for _ in range(4)] for _ in range(4)] for _ in range(n + 1)]
memo[0][3][3][3] = 1
for length in range(n):
    for s3 in range(4):  # 一番最後の文字
        for s2 in range(4):  # 最後から2番目の文字
            for s1 in range(4):  # 最後から3番目の文字
                # if memo[length][s3][s2][s1] == 0: continue
                # 新しく追加する文字
                for s4 in range(4):
                    # ダメな条件の時はcontinue
                    if s4 == 2 and s3 == 1 and s2 == 0: continue
                    if s4 == 2 and s3 == 0 and s2 == 1: continue
                    if s4 == 1 and s3 == 2 and s2 == 0: continue
                    if s4 == 2 and s3 == 1 and s1 == 0: continue
                    if s4 == 2 and s2 == 1 and s1 == 0: continue
                    
                    memo[length + 1][s4][s3][s2] += memo[length][s3][s2][s1]
                    memo[length + 1][s4][s3][s2] %= mod
ans = 0
for i in range(4):
    for j in range(4):
        for k in range(4):
            ans += memo[n][i][j][k]
            ans %= mod

print(ans)
# Original solution
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

    dp = [defaultdict(int) for _ in range(N)]
    for c in 'ACGT':
        dp[0][c + 'XX'] = 1

    for i in range(1, N):
        for s, v in list(dp[i - 1].items()):
            for c in 'AT':
                dp[i][c + s[:2]] = (dp[i][c + s[:2]] + v) % MOD
            if not (s[1] == 'A' and s[0] == 'C'):
                dp[i]['G' + s[:2]] = (dp[i]['G' + s[:2]] + v) % MOD
            if (
                not (s[1] == 'A' and s[0] == 'G')
                and not (s[1] == 'G' and s[0] == 'A')
                and not (s[2] == 'A' and s[1] == 'G')
                and not (s[2] == 'A' and s[0] == 'G')
            ):
                dp[i]['C' + s[:2]] = (dp[i]['C' + s[:2]] + v) % MOD

    ans = sum(dp[N - 1].values()) % MOD
    print(ans)

    return


if __name__ == '__main__':
    main()


# Optimized solution
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

    dp = [defaultdict(int) for _ in range(N)]
    for c in 'ACGT':
        dp[0][c + 'XX'] = 1

    for i in range(1, N):
        for s, v in list(dp[i - 1].items()):
            t = s[:2]
            for c in 'AT':
                dp[i][c + t] = (dp[i][c + t] + v) % MOD
            if not (s[1] == 'A' and s[0] == 'C'):
                dp[i]['G' + t] = (dp[i]['G' + t] + v) % MOD
            if (
                not (s[1] == 'A' and s[0] == 'G')
                and not (s[1] == 'G' and s[0] == 'A')
                and not (s[2] == 'A' and s[1] == 'G')
                and not (s[2] == 'A' and s[0] == 'G')
            ):
                dp[i]['C' + t] = (dp[i]['C' + t] + v) % MOD

    ans = sum(dp[N - 1].values()) % MOD
    print(ans)

    return


if __name__ == '__main__':
    main()
# Original solution
n = int(eval(input()))
dp = [[0]*4 for i in range(n+1)]
mod = 10**9+7

dp[0][0] = dp[0][1] = dp[0][2] = dp[0][3] = 1
dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = 4

for i in range(2,n):
    for j in range(4):
        dp[i][j] = sum(dp[i-1])%mod
    dp[i][1] -= dp[i-2][0]
    dp[i][2] -= (dp[i-2][0] + dp[i-2][1])
    if i >= 3:
        dp[i][2] -= 3*dp[i-3][0]
        dp[i][1] += dp[i-3][1]
        

print((sum(dp[n-1])%mod))

# Optimized solution
n = int(eval(input()))

mod = 10**9 + 7

a = [0]*n
c = [0]*n
g = [0]*n
t = [0]*n

a[0] = c[0] = g[0] = t[0] = 1
a[1] = c[1] = g[1] = t[1] = 4
a[2], c[2], g[2], t[2] = 16, 14, 15, 16

for i in range(3, n):
    v = (a[i-1] + c[i-1] + g[i-1] + t[i-1]) % mod
    a[i] = v
    c[i] = (v - a[i-2] - g[i-2] - 3*a[i-3]) % mod
    g[i] = (v - a[i-2] + g[i-3]) % mod
    t[i] = v
print(((a[n-1] + c[n-1] + g[n-1] + t[n-1]) % mod))
# Original solution
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=list(map(int,i().split()))
  if l>=r:s+=r;x+=[[k,l-r]]
  else:s+=l;y+=[[n-k,r-l]]*(k<n)
 for x in x,y:
  x.sort();h=[]
  for k,d in x:
   heappush(h,d)
   if len(h)>k:heappop(h)
  for d in h:s+=d
 print(s)

# Optimized solution
####################
####################
####################
####################
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=list(map(int,i().split()))
  if l>=r:x+=[[k,l,r]]
  else:y+=[[n-k,r,l]]
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   if k:s+=l;heappush(h,l-r)
   else:s+=r
   if len(h)>k:s-=heappop(h)
 print(s)
# Original solution
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*list(map(int,i().split()))];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   s+=r
   if k:s+=l-r;heappush(h,l-r)
   if len(h)>k:s-=heappop(h)
 print(s)

# Optimized solution
from heapq import*
i=input
for s in[0]*int(i()):
 n,*x=int(i()),[],[]
 for _ in'_'*n:k,l,r=t=[*list(map(int,i().split()))];x[l>r]+=[[[n-k,r,l],t][l>r]]
 for x in x:
  h=[]
  for k,l,r in sorted(x):heappush(h,l-r);s+=l-(k<len(h)and heappop(h))
 print(s)
# Original solution
from collections import deque
from heapq import heappush, heappushpop
import sys
input = sys.stdin.readline

def calc(camels):
    camels = deque(sorted(camels, key=lambda x: x[0]))
    N = len(camels)
    heap = []
    while camels and camels[0][0] == 0:
        camels.popleft()
    for i in range(1, N+1):
        while camels and camels[0][0] == i:
            _, x = camels.popleft()
            if len(heap) < i:
                heappush(heap, x)
            elif heap[0] < x:
                heappushpop(heap, x)
    for _, x in camels:
        if len(heap) < N:
            heappush(heap, x)
        elif heap[0] < x:
            heappushpop(heap, x)
    return sum(heap)

T = int(eval(input()))
for _ in range(T):
    N = int(eval(input()))
    s = 0
    ans = 0
    first = []
    second = []
    for i in range(N):
        K, L, R = list(map(int, input().split()))
        if L >= R:
            first.append((K, L - R))
            ans += R
        else:
            second.append((N - K, R - L))
            ans += L
    ans += calc(first) + calc(second)
    print(ans)

# Optimized solution
from heapq import heappush, heappop
import sys
input = sys.stdin.readline

def calc(camels, N):
    camels.sort(key=lambda x: x[0])
    heap = []
    for i, x in camels:
        heappush(heap, x)
        if len(heap) > i:
            heappop(heap)
    return sum(heap)

T = int(eval(input()))
for _ in range(T):
    N = int(eval(input()))
    s = 0
    ans = 0
    first = []
    second = []
    for i in range(N):
        K, L, R = list(map(int, input().split()))
        if L >= R:
            first.append((K, L - R))
            ans += R
        else:
            second.append((N - K, R - L))
            ans += L
    ans += calc(first, N) + calc(second, N)
    print(ans)
# Original solution
import heapq
T=int(eval(input()))

for _ in range(T):
  N=int(eval(input()))
  
  llist=[]
  rlist=[]
  base=0
  for _ in range(N):
    K,L,R=list(map(int,input().split()))
    base+=min(L,R)
    if L>R:
      llist.append((K,L-R))
    elif L<R:
      rlist.append((N-K,R-L))
      
  llist.sort()
  rlist.sort()      
  #print(base)
  #print(llist)
  #print(rlist)
  
  hq_left=[]
  for i,l in llist:
    heapq.heappush(hq_left,l)
    if len(hq_left)>i:
      heapq.heappop(hq_left)
  hq_right=[]
  for i,r in rlist:
    heapq.heappush(hq_right,r)
    if len(hq_right)>i:
      heapq.heappop(hq_right)
      
  answer=base
  while hq_left:
    answer+=heapq.heappop(hq_left)
  while hq_right:
    answer+=heapq.heappop(hq_right)
    
  print(answer)

# Optimized solution
import heapq
T=int(eval(input()))

for _ in range(T):
  N=int(eval(input()))
  
  llist=[]
  rlist=[]
  base=0
  for _ in range(N):
    K,L,R=list(map(int,input().split()))    
    if L>R:
      llist.append((K,L-R))
      base+=R
    elif L<R:
      rlist.append((N-K,R-L))
      base+=L
    else:
      base+=L
      
  llist.sort()
  rlist.sort()      
  #print(base)
  #print(llist)
  #print(rlist)
  
  hq_left=[]
  for i,l in llist:
    heapq.heappush(hq_left,l)
    if len(hq_left)>i:
      heapq.heappop(hq_left)
  hq_right=[]
  for i,r in rlist:
    heapq.heappush(hq_right,r)
    if len(hq_right)>i:
      heapq.heappop(hq_right)
      
  answer=base
  while hq_left:
    answer+=heapq.heappop(hq_left)
  while hq_right:
    answer+=heapq.heappop(hq_right)
    
  print(answer)