Harryxun/stf_run huggingface dataset:
# -*- coding: utf-8 -*-
import numpy as np 
import math

# 入力
N = int(input())
A = input()

A = np.array(A.split()).astype('int')
ones = np.ones([N, N])
B = (A*ones)
for i in range(N):
    B[i, i] = 0
B = B[np.where(B != 0, True, False)].reshape(N, N-1)
B.sort()

def comb(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
      
def uniq_2_comb(N, ar):
    u = np.unique(ar, return_index=True)[1]
    u = np.concatenate([u, np.array([N-1])])
    ans = 0
    for i in range(len(u)-1):
        n = u[i+1] - u[i]
        ans += comb(n, 2)
    return ans

ans_ar = np.apply_along_axis(lambda x : uniq_2_comb(N, x), 1, B)

for a in ans_ar:
    print(a)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import collections
import math

# 入力
N = int(input())
A = list(input().split())

c = collections.Counter(A)

def comb(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

comb_sum = 0
for i in c:
    comb_sum += comb(c[i], 2)
     
for a in A:
    ans = comb_sum
    if c[a] >= 2:
        ans -= (c[a] - 1)
    print(ans)
from collections import Counter
import numpy as np
import pandas as pd
N = int(input())
list = [input() for _ in range(0,N)]
counted = Counter(list)
res_max= counted.most_common()[0][1]

ans = []
for k, v in counted.items():
    if k == v:
        ans.append(k)

ans.sort()
print(*ans, sep="\n")
    


### FIXED CODE ###

from collections import Counter


N = int(input())
list = [input() for _ in range(0,N)]
counted = Counter(list)
res_max= counted.most_common()[0][1]
ans = []
for k, v in counted.items():
    if v == res_max:
        ans.append(k)

ans.sort()
print(*ans, sep="\n")
n, m = map(int,input().split())
dangerList = [int(input()) for i in range(m)]
answerList = [0] * (n+2)
answerList[0] = 1
nextDanger = dangerList.pop(0)
for i in range(n):
  if i == nextDanger:
    if len(dangerList) > 0:
    	nextDanger = dangerList.pop(0)
  else:
    answerList[i+1] = (answerList[i+1] + answerList[i]) % 1000000007
    answerList[i+2] = (answerList[i+2] + answerList[i]) % 1000000007
print(answerList[n])

### FIXED CODE ###

n, m = map(int,input().split())
dangerList = [int(input()) for i in range(m)]
answerList = [0] * (n+2)
answerList[0] = 1
nextDanger = n + 2
if len(dangerList) > 0:
  nextDanger = dangerList.pop(0)
for i in range(n):
  if i == nextDanger:
    if len(dangerList) > 0:
    	nextDanger = dangerList.pop(0)
  else:
    answerList[i+1] = (answerList[i+1] + answerList[i]) % 1000000007
    answerList[i+2] = (answerList[i+2] + answerList[i]) % 1000000007
print(answerList[n])
import numpy as np
n = int(input())
a = np.empty((0,2),int)
for i in range(n):
    b = np.array([[int(i) for i in input().split()]])
    a = np.append(a,b,axis=0)
a = a[np.argsort(a[:, 1])]
ans = "Yes"
k = 0
for i in range(len(a)):
    k += a[i,0]
    if k > a[i,1]:
        ans = "No"
        break
print(ans)

### FIXED CODE ###

import math
from fractions import gcd
a,b,c,d = map(int,input().split())
x = b//c - (a-1)//c
y = b//d - (a-1)//d
l = c * d // gcd(c,d)
z = b//l - (a-1)//l
print(b-a+1-x-y+z)
N, M = map(int, input().split())
matrix=[[0]*N for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    matrix[a-1][b-1]=1
    matrix[b-1][a-1]=1
import itertools 
count=0
result=1
for i in itertools.permulations(range(1, N+1)):
    if i==1:
        for j in range():
            result+=matrix[i[j]][i[j+1]]
            if result=1:
                count+=1
            else:
                result=1
print(count)

### FIXED CODE ###


import itertools

N, M = map(int, input().split())
adj_matrix = [[0]* N for _ in range(N)]

for i in range(M): #隣接行列
    a, b = map(int, input().split())
    adj_matrix[a-1][b-1] = 1
    adj_matrix[b-1][a-1] = 1

cnt = 0

for each in itertools.permutations(range(N)):
    if each[0] != 0:
        break
    factor = 1
    for i in range(N-1):
        factor *= adj_matrix[each[i]][each[i+1]]
    cnt += factor

print(cnt)
a.b = list(map(int,input().split()))

area = a * b
length = 2 * (a + b)

print(area,end=" ")
print(length)

### FIXED CODE ###

a,b = list(map(int,input().split()))

area = a*b
length = 2 * (a+b)

print(area,end=" ")
print(length)
a = 1
while a*2 <= int(input()):
    a*=2
print(a)

### FIXED CODE ###

a = 1
n=int(input())
while a*2 <= n:
    a*=2
print(a)
n, l = map(int, input().split())
sl = []
for i in range(n):
    s = input()
    sl.append(s)
sl.sort()
"print(sl)
ans = ""
for i in range(n):
    ans += sl[i]
print(ans)

### FIXED CODE ###

n, l = map(int, input().split())
sl = []
for i in range(n):
    s = input()
    sl.append(s)
sl.sort()
#print(sl)
ans = ""
for i in range(n):
    ans += sl[i]
print(ans)
# -*- coding: utf-8 -*-

N = int(input())

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

mul = A[0]
for i in A[1:]:
    mul *= i
    
    if mul > 1000000000000000000:
        print(-1)
        exit(-1)

print(mul)

### FIXED CODE ###

# -*- coding: utf-8 -*-

input_list = input().split(" ")
print(int(input_list[0]) * int(input_list[1]))
import sys

sys.setrecursionlimit(2*10**5)
input = sys.stdin.readline

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for _ in range(n-1):
    a, b = map(lambda x: int(x)-1, input().split())
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for _ in range(q):
    p, x = map(int, input().split())
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i == parent:
            continue
        dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for a, b in [[int(i)-1 for i in input().split()] for _ in range(n-1)]:
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for p, x in [[int(i) for i in input().split()] for _ in range(q)]:
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i == parent:
            continue
        dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))
S = input().strip()

def check(l):
  for i in range(len(l)-1):
    if l[i] == l[i+1]:
      return False
  return True

# 一番最後だけ分割する
def hoge(l):
  next_stack = []
  for i in range(1, len(l[-1])):
    next_list = l[:-1] + [l[-1][:i], l[-1][i:]]
    if check(next_list):
      next_stack.append(next_list)
  return next_stack
      
stack = [[S]]
max_len = 1
while True:
  if len(stack) == 0:
    break
  now = stack.pop(0)
  if len(now)+len(now[-1])-2 < max_len:
    continue
  #print('----------')
  #print(now)
  #print(hoge(now))
  max_len = max(max_len, len(now))
  stack += hoge(now)
  
print(max_len)

### FIXED CODE ###

S = input().strip()

prev = ''
now = ''
result = 0
for c in S:
  if len(prev) == 0:
    prev = c
    result += 1
    continue
  now += c
  if prev == now:
    continue
  else:
    prev = now
    now = ''
    result += 1
print(result)
def main():
  N = int(input())
  S = input()
  R = 0
  B = 0
  for i in range(0,N):
    if S[i] == "R":
      R = R + 1
    else:
      B = B + 1
	if R > N/2:
      print("Yes")
      return
    elif B > N/2:
      print("No")
      return
      
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    R = 0
    B = 0
    for i in range(0,N):
        if S[i] == "R":
            R = R + 1
        else:
            B = B + 1
        if R > N/2:
            print("Yes")
            return
        elif B > N/2:
            print("No")
            return
    print("No")
    
if __name__ == '__main__':
    main()
#input
N = int(input())
A = list(map(int,input().split()))

count = 0
flag = 0
 
#loop
while(1):
  for i in range(N):
    
    if A[i] %2 == 1:
      flag = 1
    else:
      temp = A[i]/2
      A[i] = temp;
  
  #judge
  if flag == 1:
    break
  else:
    count +=1
 
print(count)

### FIXED CODE ###

s = input()
print(s.count("1"))
n = int(input())
A = list(map(int, input().split()))

import math
def gcd(list):
    gcd = list[0]
    for a in list:
        gcd = math.gcd(gcd, a)
    return gcd

max_gcd = 0
for i in range(n):
    Ai = A.pop(i)
    max_gcd = max(max_gcd, gcd(A))
    A.insert(i, Ai)

print(max_gcd)

### FIXED CODE ###

import fractions
n = int(input())
a = list(map(int, input().split()))
forward = [0]
back =[0]
for i in range(0,n-1):
    forward.append(fractions.gcd(forward[i], a[i]))
    back.append(fractions.gcd(back[i], a[n-i-1]))
ans = 0
for i in range(n):
    ans = max(ans, fractions.gcd(forward[i], back[n-1-i]))
print(ans)
import  sympy
n = int(input())
a = list(map(int,input().split()))
d = {}
for i in [0,1]:
    for j in sympy.divisors(a[i]):
        d[j] = 2
key = list(d.keys())
for i in range(n):
    c = key[:]
    b = sympy.divisors(a[i])
    for j in c:
        if not(j in b):
            d[j] -= 1
            if d[j] == 0:
                key.remove(j)
key = sorted(key,reverse = True)
print(key[0])


### FIXED CODE ###

import math
n = int(input())
a = list(map(int,input().split()))
r ,l = [0] * (n),[0] * (n)
l[0] = 0
r[n-1] = 0
for i in range(1,n):
    l[i] = math.gcd(l[i-1],a[i-1])
    r[n-i-1] = math.gcd(r[n-i],a[n-i])
m = [0] * n
for i in range(n):
    m[i] = math.gcd(l[i],r[i])
print(max(m))
n,s=int(input()),list(input())
c=0
for i in range(len(s)):
  h=len(set(s[:i])&(s[i:]))
  c=max(c,h)
print(c)

### FIXED CODE ###

n,s,c=int(input()),list(input()),0
for i in range(n):
  h=len(set(s[:i])&set(s[i:]))
  c=max(c,h)
print(c)
#dpp
MOD = 10**9+7
n = int(input())
dp = [[1 for _ in range(2)] for _ in range(n)]
edges = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	edges[x-1].append(y-1)
	edges[y-1].append(x-1)

def dfs(le, ro):
	for ed in edges[le]:
		if ed == ro:
			continue
		dfs(ed, le)
		dp[le][0] = (dp[le][0] * (dp[ed][0] + dp[ed][1])) % MOD
		dp[le][1] = (dp[le][1] * dp[ed][0]) % MOD
	return

dfs(0, -1)
print((dp[0][0] + dp[0][1]) % MOD)

### FIXED CODE ###

#dpp
import sys
sys.setrecursionlimit(10**7)
MOD = 10**9+7
n = int(input())
dp = [[1 for _ in range(2)] for _ in range(n)]
edges = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	edges[x-1].append(y-1)
	edges[y-1].append(x-1)

def dfs(le, ro):
	for ed in edges[le]:
		if ed == ro:
			continue
		dfs(ed, le)
		dp[le][0] = (dp[le][0] * (dp[ed][0] + dp[ed][1])) % MOD
		dp[le][1] = (dp[le][1] * dp[ed][0]) % MOD
	return

dfs(0, -1)
print((dp[0][0] + dp[0][1]) % MOD)
import math
A, B, H, M = map(int,input().split())
n = 10
# 長針の角度
long = 6 * M
# 短針の角度
short = 30*(H) + 0.5*M
if long < short:
    theta = short - long
if long > short:
    theta = lomg - short
if theta > 180:
    theta = 360 - theta
cos = math.cos(math.radians(theta))
x = A**2 + B**2 - 2*A*B*cos
y = math.floor(x * 10 ** n) / (10 ** n)
print(math.sqrt(y))


### FIXED CODE ###

import math
from decimal import *
A, B, H, M = map(int,input().split())
# 長針の角度
long = 6 * M
# 短針の角度
short = 30*(H) + 0.5*M
theta = abs(long - short)
if theta > 180:
    theta = 360 - theta
cos = math.cos(math.radians(theta))
x = A**2 + B**2 - 2*A*B*cos
x = math.sqrt(x) # 平方根に変換
n = 10 # 小数点10位以下を切り捨て
y = Decimal(str(x)).quantize(Decimal(str(10**(n*-1))), rounding=ROUND_DOWN)
print(y)
n = int(input())
xn = map(int,input().split())
k = 0
for i in range(1,n+1)
	if xn[i-1] != i:
    	k += 1
print("NO" if k > 2 else "YES")

### FIXED CODE ###

n = input()
list = [int(x) for x in input().split()]
end = 0
for i, num in enumerate(list):
    if num != i + 1:
        end += 1
    if end > 2:
        break

if end <= 2:
    print("YES")
else:
    print("NO")
ipt=list(map(int, input().split()))

N=ipt[0]
K=ipt[1]
h=ipt[2:]

cnt=0
for n in range(N):
    if h[n]>=K:
        cnt+=1

print(cnt)


### FIXED CODE ###

N,K=map(int, input().split())
h=list(map(int, input().split()))

cnt=0
for n in range(N):
    if h[n]>=K:
        cnt+=1

print(cnt)
x, y, z = map(int(input().split()))
print(z, x, y)

### FIXED CODE ###

x, y, z = map(int, input().split())
print(z, x, y)
from numba import njit

N, K = map(int, input().split())
*A, = map(int, input().split())
*F, = map(int, input().split())
A, F = sorted(A), sorted(F, reverse=True)

@njit
def cond(x):
    k = 0
    for a, f in zip(A, F): k += max(a - (x // f), 0)
    return True if k <= K else False 

MIN = -1
MAX = 10**12 + 1
left, right = MIN, MAX # search range
while right - left > 1:
    mid = (left + right) // 2
    if cond(mid): right = mid
    else: left = mid
print(right)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())
*F, = map(int, input().split())
A, F = sorted(A), sorted(F, reverse=True)

def cond(x):
    k = 0
    for a, f in zip(A, F): k += max(a - (x // f), 0)
    return True if k <= K else False 

MIN = -1
MAX = 10**12 + 1
left, right = MIN, MAX # search range
while right - left > 1:
    mid = (left + right) // 2
    if cond(mid): right = mid
    else: left = mid
print(right)
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def check(n):
        if n == 1:
            return False
        i = 2
        while i*i <= n:
            if n%i == 0:
                return False
            i += 1
        return True
    f = [0 for i in range(10001)]
    for i in range(1,10001):
        f[i] += f[i-1]
        if check(i):
            if check((i+1)//2):
                f[i] += 1
    q = I()
    for i in range(q):
        l,r = LI()
        print(f[r]-f[l-1])

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def check(n):
        if n == 1:
            return False
        i = 2
        while i*i <= n:
            if n%i == 0:
                return False
            i += 1
        return True
    f = [0 for i in range(100001)]
    for i in range(1,100001):
        f[i] += f[i-1]
        if check(i):
            if check((i+1)//2):
                f[i] += 1
    q = I()
    for i in range(q):
        l,r = LI()
        print(f[r]-f[l-1])

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()
has_seven = False
N = str(raw_input())
for i in range(len(N)):
  	if N[i] == '7':
    	has_seven = True
    break

if has_seven:
	print("Yes")
else:
	print("No")




### FIXED CODE ###


has_seven = False
N = str(input())
for i in range(len(N)):
  if N[i] == '7':
      has_seven = True
      break

if has_seven:
  print("Yes")
else:
  print("No")
N, K = list(map(int,input().split()))
k = K + 1
hp = 0
H = list(map(int,input().split()))
Hs = sorted(H,reverse = True)
for i in range(0,K):
  Hs[i] = 0
for i in range(k,N):
  hp += Hs[i]

### FIXED CODE ###

N, K = list(map(int,input().split()))
k = K - 1
H = list(map(int,input().split()))
Hs = sorted(H,reverse = True)
if K <= N:
  for i in range(0,K):
    Hs[i] = 0
  print(sum(Hs))
if K > N:
  print(0)
def numS(S):
    x=len(S)
    if x<4:
        return 0
    T=S[1:]
   # print(T)
   l=x-1
    sum=0
    now=S[0]
    for i in range(l):
        now2=T[i]
    #    print(now2)
        if now2!=now:
            for j in range(i+1,l):
                now3=T[j]
     #           print(now,now2,now3)
                if now3!=now2 and now3!=now:
      #              print(i,j)
                    sum+=1
                    if 2*i+1==j:
                        sum-=1
    return numS(T)+sum
n=int(input())
S=input()
print(numS(S))

### FIXED CODE ###

n=int(input())
S=input()
R={}
G={}
B={}
r=0
g=0
b=0
for i in range(n):
    if S[i] == 'R':
        R[i] = None
    elif S[i] == 'G':
        G[i] = None
    else:
        B[i] = None
cnt=len(R)*len(G)*len(B)
for b in B:
    for g in G:
        if (b+g)/2 in R:
            cnt-=1
for b in B:
    for r in R:
        if (b+r)/2 in G:
            cnt-=1
for r in R:
    for g in G:
        if (r+g)/2 in B:
            cnt-=1
print(cnt)
arrayNM = list(map(int, input.split()))
array = list(map(int, input.split()))
tokuhyousuu = 1 / (4 * array[1])
ninnkiCounter = 0
for num in array:
  if ((float)num >= tokuhyosuu):
    ninnkiCounter += 1
    

if (arrayNM[1] <= ninnkiCounter):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

arrayNM = list(map(int, input().split()))
array = list(map(int, input().split()))
soutoku = 0
for num in array:
  soutoku += num
tokuhyousuu = soutoku / (4 * float(arrayNM[1]))
ninnkiCounter = 0
for num in array:
  if (float(num) >= tokuhyousuu):
    ninnkiCounter += 1
    

if (arrayNM[1] <= ninnkiCounter):
  print("Yes")
else:
  print("No")
a,b,c=map(int,input().split())
if a==b==c:
    print(-1)
total=0
else:
    while True:
        x=a/2
        y=b/2
        z=c/2
        a=y+z
        b=x+z
        c=x+y
        total+=1
        if a%2!=0 or b%2!=0 or c%2!=0:
            print(total)
            break

### FIXED CODE ###

a,b,c=map(int,input().split())
if a%2!=0 or b%2!=0 or c%2!=0:
    print(0)
elif a==b==c:
    print(-1)
else:
    total=0
    while True:
        x=a/2
        y=b/2
        z=c/2
        a=y+z
        b=x+z
        c=x+y
        total+=1
        if a%2!=0 or b%2!=0 or c%2!=0:
            print(total)
            break
n = int(input())
v = [int(i) for i in input().split()]

ki = v[::2]
gu = v[1::2]

ki = Counter(ki)
gu = Counter(gu)

ki = ki.most_common()
gu = gu.most_common()

ans = 0

if ki[0][0] == gu[0][0]:
    if len(ki) == 1 and len(gu) == 1:
        ans = int(n / 2)
    else:
        if ki[1][1] > gu[1][1]:
            ans = n - ki[1][1] - gu[0][1]
        else:
            ans = n - ki[0][1] - gu[1][1]
else:
    ans = n - ki[0][1] - gu[0][1]

print("答え",ans)

### FIXED CODE ###

from collections import Counter
def main(n,v):
    # n = int(input())
    # v = list(map(int, input().split()))
    odd = Counter(v[0::2]).most_common(2) + [(0, 0)]
    even = Counter(v[1::2]).most_common(2) + [(0, 0)]

    n_half = int(n / 2)

    if (len(odd) == 1 and len(even) == 1) and odd[0][0] == even[0][0]:
        ans = n_half
    elif odd[0][0] == even[0][0]:
        ans = min(n_half - odd[0][1] + n_half - even[1][1],\
                n_half - odd[1][1] + n_half - even[0][1])
    else:
        ans = n_half - odd[0][1] + n_half - even[0][1]

    print(ans)
    return 0

if __name__ == "__main__":
    n = int(input())
    v = list(map(int, input().split()))
    main(n,v)
atcoder-tools: The pre-rendered templates are not found.import numpy as np

N, M = map(int, input().split())
AC_or_not = np.array([0] * N)
n_penalty = np.array([0] * N)

for _ in range(M):
    prob, wa_ac = input().split()
    prob = int(prob) - 1
    if wa_ac == 'AC':
        AC_or_not[prob] = 1
    else:
        if not AC_or_not[prob]:
            n_penalty[prob] += 1

print(sum(AC_or_not), sum(n_penalty * AC_or_not))

### FIXED CODE ###

import numpy as np

N, M = map(int, input().split())
AC_or_not = np.array([0] * N)
n_penalty = np.array([0] * N)

for _ in range(M):
    prob, wa_ac = input().split()
    prob = int(prob) - 1
    if wa_ac == 'AC':
        AC_or_not[prob] = 1
    else:
        if not AC_or_not[prob]:
            n_penalty[prob] += 1

print(sum(AC_or_not), sum(n_penalty * AC_or_not))
import numpy as np
import sys
n  = 45
f = [-1 for i in range(45)]

def fib(n):
    global f

    if (n == 0):
        return 1
    elif (n == 1):
        return 1
    elif(f[n] == -1):
        f[n] = fib(n - 1) + fib(n - 2)

    return f[n]

if __name__ == "__main__":


    n = input("input number: ")
    n = int(n)
    #print(type(n))
    print(fib(n))



### FIXED CODE ###


f = [-1 for i in range(45)]
f[0] = f[1] = 1

def fib(n):
    global f
    for i in range(2,n+1):
        f[i] = f[i - 1] + f[i - 2]
        #print(i,f[i])
    return f[n]

if __name__ == "__main__":
    n = input()
    n = int(n)
    #print(type(n))
    print(fib(n))
N, K = map(int, input().split())
S = list(input())
S[K] = S[K].lower()
print(''.join(S))

### FIXED CODE ###

N, K = map(int, input().split())
S = list(input())
S[K-1] = S[K-1].lower()
print(''.join(S))
n = int(input())
arr = []
for i in range(n-1):
    arr.append([int(s) for s in input().split(" ")])

childNodeNums = [0 for i in range(n)]
childNodeStatus = [-1 for i in range(n)]
nodeLines = [[] for i in range(n - 1)]


def prepare(n, arr):
    s = [[] for i in range(n)]
    for ar in arr:
        s[ar[0] - 1].append(ar[1] - 1)
        s[ar[1] - 1].append(ar[0] - 1)
    return s


# x为记录入边的颜色
def dfs(currentNode, arr, x):
    childNodes = arr[currentNode]
    if len(childNodes) == 0:
        return

    childNodeNums[currentNode] = childNodeNums[currentNode] + len(arr[currentNode])
    childNodeStatus[currentNode] = 1

    kk = 0
    for i, childNodeIndex in enumerate(childNodes):

        if childNodeStatus[childNodeIndex] == -1:
            kk = kk + 1
            if x == kk:
                kk = kk + 1
            nodeLines[currentNode].append(kk)
            dfs(childNodeIndex, arr, kk)



data = prepare(n, arr)
dfs(0, data, -1)

print(max(childNodeNums))

for ar in nodeLines:
    for r in ar:
        print(r)


### FIXED CODE ###

from sys import setrecursionlimit


def genid(a, b):
    if b < a:
        a, b = b, a
    return a * 100000 + b


def paint(currentNode, usedColor, parentNode, edges, colors):
    color = 1
    for childNode in edges[currentNode]:
        if childNode == parentNode:
            continue
        if color == usedColor:
            color += 1
        colors[genid(currentNode, childNode)] = color
        paint(childNode, color, currentNode, edges, colors)
        color += 1


setrecursionlimit(100000)

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]

edges = [[] for _ in range(N)]
for a, b in ab:
    edges[a - 1].append(b - 1)
    edges[b - 1].append(a - 1)

colors = {}
paint(0, -1, -1, edges, colors)

print(max(len(e) for e in edges))
for a, b in ab:
    print(colors[genid(a - 1, b - 1)])
N=int(input())
A=map(int,input().split())
m=10**9+7
r=1
C=[0,0,0]
for a in A:
  i=C.index(a)
  r=r*sum([1 if c==a else 0 for c in C])%m
  C[i]+=1
print(r)


### FIXED CODE ###

N=int(input())
A=map(int,input().split())
m=10**9+7
r=1
C=[0,0,0]
for a in A:
    try:
        i=C.index(a)
        r=r*sum([1 if c==a else 0 for c in C])%m
        C[i]+=1
    except:
        print(0)
        exit()
print(r)
s = input()

ans = ''
for i in s:
    if i == 'B':
        ans = ans[:-1]
    else
        ans += i
print(ans)

### FIXED CODE ###

s = input()

ans = ''
for i in s:
    if i == 'B':
        ans = ans[:-1]
    else:
        ans += i
print(ans)