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

def main():
    n,q = map(int,raw_input().split())

    ds = DisjointSet(n)

    for i in xrange(q):
        com,x,y = map(int,raw_input().split())
        if com:
            if ds.root[x] == ds.root[y]:
                print 1
            else:
                print 0
        else:
            ds.unite(x,y)

class DisjointSet():
    def __init__(self,n):
        self.n = n
        self.root = range(n)
        self.parent = [-1]*n
        self.rank = [0]*n

    def findSet(self,x):
        if self.parent[x] == -1:
            return x
        else:
            p = self.findSet(self.parent[x])
            self.parent[x] = p

    def unite(self,x,y):
        if self.rank[x] > self.rank[y]:
            for z in [u for u in xrange(self.n) if self.root[u] == self.root[y]]:
                self.parent[z] = self.root[x]
                self.root[z] = self.root[x]
                self.rank[z] = self.rank[x]
        elif self.rank[x] < self.rank[y]:
            for z in [u for u in xrange(self.n) if self.root[u] == self.root[x]]:
                self.parent[z] = self.root[y]
                self.root[z] = self.root[y]
                self.rank[z] = self.rank[y]
        else:
            for z in [u for u in xrange(self.n) if self.root[u] == self.root[x]]:
                self.parent[z] = self.root[y]
                self.root[z] = self.root[y]
                self.rank[z] = self.rank[y]+1

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n,q = map(int,raw_input().split())

    ds = DisjointSet(n)

    for i in xrange(q):
        com,x,y = map(int,raw_input().split())
        if com:
            ds.findSet(x)
            ds.findSet(y)
            if ds.parent[x] == ds.parent[y]:
                print 1
            else:
                print 0
        else:
            ds.findSet(x)
            ds.findSet(y)
            ds.unite(x,y)

class DisjointSet():
    def __init__(self,n):
        self.n = n
        self.parent = range(n)

    def findSet(self,x):
        if self.parent[x] == x:
            return x
        else:
            p = self.findSet(self.parent[x])
            self.parent[x] = p
            return p

    def unite(self,x,y):
        if self.parent[y] > self.parent[x]:
            self.parent[self.parent[y]] = self.parent[x]
        else:
            self.parent[self.parent[x]] = self.parent[y]

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

def main():
    a,b,n = map(int, input().split())
    
    ans = 0
    if n < b:
        ans = a*(n/b)
    
    else:
        for i in range(1,int(n//b+1)):
            x = b*i-1
            ans = max(ans, a*((x-(i-1)*b)/b))
    
    print(int(ans//1))

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    a,b,n = map(int, input().split())
    
    ans = 0
    if n < b:
        ans = a*(n/b)
    
    else:
        for i in range(1,int(n//b+1)):
            x = b*i-1
            ans = max(ans, a*((x-(i-1)*b)/b))
            break
    
    print(int(ans//1))

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

s=input()
t=input()

ls=len(s)
lt=len(t)

for i in range(lt):
  if (t[i] in s) == False:
    print(-1)
    exit()

si,ti=0,0
while ti < lt:
  if s[si%ls]==t[ti]:
    ti += 1
  si += 1
print(si)


### FIXED CODE ###

import bisect

s=input()
t=input()

sl=len(s)
tl=len(t)

r="abcdefghijklmnopqrstuvwxyz"
p=[[] for i in range(26)]

for i in range(sl):
  p[r.find(s[i])].append(i)

for i in range(26):
  if len(p[i])>0:
    p[i].append(p[i][0]+sl)

s=set()
for i in range(tl):
  s.add(t[i])
for c in s:
  if len(p[r.find(c)]) == 0:
     print(-1)
     exit()

ti, si = 0, -1
while ti < tl:
  si +=  p[r.find(t[ti])][bisect.bisect_right(p[r.find(t[ti])], si%sl)] - si%sl
  ti += 1

print(si+1)
### BUGGY CODE ###

N = int(input())
L = input().split()
L = [int(L[i]) for i in range(len(L))]

tri = 0
for i in range(N):
  for j in range(i+1,N):
    for k in range(j+1,N):
      if L[i] < L[j] + L[k] and L[j] < L[i] + L[k] and L[k] < L[i] + L[j]:
        tri += 1
print(tri)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt = 0

import bisect
for i in range(N):
  for j in range(i+1,N-1):
    insert = bisect.bisect_left(L,L[i]+L[j]) -j -1
    cnt += insert
        
print(cnt)
### BUGGY CODE ###

import numpy as np

N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = 0
C = set()
D = set()
for i in range(M):
  count = 0
  boo = True
  while(boo):
    for j in range(M):
      if i != j:
        if(count == 0):
          C.add(a[j])
          C.add(b[j])
          count += 1
        if C <= {a[j]} or C <= {b[j]}:
          C.add(a[j])
          C.add(b[j])
    if(C in D):
      boo = False
      break
    else:
      D = C
  if(len(C) == N):
    ans += 1
print(ans)

### FIXED CODE ###

import numpy as np
 
N, M = (list(map(int, input().split())))
a = np.array([0]*M)
b = np.array([0]*M)
for i in range(M):
  a[i], b[i] = (input().split())
ans = M
for i in range(M):
  C = set()
  D = set()
  count = 0
  while(True):
    for j in range(M):
      if not i == j:
        if(count == 0):
          C.add(a[j]) 
          C.add(b[j])
          count += 1  
        if a[j] in C or b[j] in C:
          C.add(a[j])
          C.add(b[j])
    if(C == D):
      break
    else:
      D = C.union(D)
  if(len(C) == N):
    ans -= 1
print(ans)
### BUGGY CODE ###


from collections import deque
INF = 10**18

def find_s(dq):
    minx = (-1, INF)
    for x in dq:
        if x[1] < minx[1]:
            minx = x
    return minx[0]

def append_dq(i, x, dq, dp1):
    while True:
        if not len(dq):
            dq.append([i, x])
            break
        lxi = dq[-1][0]
        if x > dp1[lxi]:
            dq.append([i, dp1[i]])
            break
        dq.pop()
    return dq

dq = deque()
N,M = map(int, input().split())
S = input().strip()
dp1 = [0] + [INF]*N
dp2 = [[] for _ in range(N+1)]
dq.append([0, 0])

for i, c in enumerate(S[1:]):
    i+=1
    dq = append_dq(i, dp1[i], dq, dp1)
    if c == "1":
        if i >= M:
            sxi = dq[0][0]
            if sxi == (i - M):
                dq.popleft()
        continue
    idx, vx = dq[0]
    if dp1[idx] == INF:
        if i >= M:
            sxi = dq[0][0]
            if sxi == (i - M):
                dq.popleft()
        continue
    dp1[i] = dp1[idx] + 1
    dp2[i] = dp2[idx] + [i-idx]
    if i >= M:
        sxi = dq[0][0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print(-1)
else:
    print(" ".join(map(str, dp2[-1])))


### FIXED CODE ###

from collections import deque
INF = 10**18

def append_dq(i, x, dq, dp1):
    while True:
        if not len(dq):
            dq.append(i)
            break
        lxi = dq[-1]
        if x > dp1[lxi]:
            dq.append(i)
            break
        dq.pop()
    return dq
dq = deque()
N,M = map(int, input().split())
S = input().strip()
dp1 = [0] + [INF]*N
dp2 = [-1 for _ in range(N+1)]
dq.append(0)
for i, c in enumerate(S[1:]):
    i+=1
    dq = append_dq(i, dp1[i], dq, dp1)
    idx = dq[0]
    if c != "1" and dp1[idx] != INF:
        dp1[i] = dp1[idx] + 1
        dp2[i] = idx
    if i >= M:
        sxi = dq[0]
        if sxi == (i - M):
            dq.popleft()
if dp1[-1] == INF:
    print(-1)
else:
    r = []
    s = N
    while True:
        if s == 0:
            break
        ns = dp2[s]
        r.append(s-ns)
        s = ns
    print(" ".join(map(str, r[::-1])))
### BUGGY CODE ###



n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
b=[0]*m
for _ in range(m):
    if b[-1:]<a[-1:]:
        temp=a.pop()
    else:
        temp=b.pop()
    temp=temp//2
    b[0]=temp
    b.sort()

print(sum(a)+sum(b))

### FIXED CODE ###

from heapq import heapify,heappop,heappush

n,m=map(int,input().split())
a=[-int(a) for a in input().split()]
heapify(a)
for _ in range(m):
    heappush(a,heappop(a)/2)
print(-sum(int(x) for x in a))
### BUGGY CODE ###

import sys
import math
from fractions import gcd
# import queue
# from collections import Counter
# from itertools import accumulate
# from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

big_prime = 1000000007

"""
# 標準入力取得
## 文字列
 =  sys.stdin.readline().rstrip()
 =  list(sys.stdin.readline().rstrip())

## 数値
 =  int(sys.stdin.readline())
 =  map(int, sys.stdin.readline().split())
 =  list(map(int, sys.stdin.readline().split()))
 = list(map(int,sys.stdin.readlines())) #縦入力
 =  [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""
n,m =  map(int, sys.stdin.readline().split())

dp=[0]*(n+1)
list_a = list(map(int,sys.stdin.readlines()))

dp[0]=1

for i in range(1,n+1):
    dp[i] = dp[i-1] + dp[i-2] #dp[-1]=0
    if i in list_a:
        dp[i]=0
ans = dp[n] % big_prime
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())
a = set([int(input()) for _ in range(M)])
INF = 1000000007

dp = [0] * (N + 1)
dp[0] = 1
if 1 not in a:
	dp[1] = 1
else:
	dp[1] = 0
for i in range(2, N + 1):
	if i in a:
		continue
	dp[i] = dp[i - 1] + dp[i - 2]
	dp[i] %= INF

print(dp[N])
### BUGGY CODE ###

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

ans = 0
while 1:
    j = -1
    for i,a in enumerate(A):
        if a >= N:
            j = i
            break
    else:
        break
    d,m = divmod(A[j],N)
    ans += d
    A[j] = m
    for i in range(N):
        if i==j: continue
        A[i] += d
print(ans)

### FIXED CODE ###

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

ans = 0
while any(map(lambda x: x >= N, a)):
    a.sort(reverse=True)
    k = (a[0] - N)//N + 1
    ans += k
    a[0] -= k*N
    for i in range(1,N):
        a[i] += k

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

n, m = map(int, input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
count = 0
for i in range(m):
    ab[i].sort()
while len(ab) > 0:
    ab = sorted(ab, key = lambda x: x[1])
    end = ab[0]
    list.sort(ab, reverse=True)
    remove = ab.index(end)
    if remove >= 1:
        while ab[remove - 1][0] < end[1]:
            remove -= 1
            if remove == 0:
                break
    del ab[(remove):]
    count += 1
print(int(count))


### FIXED CODE ###

n, m = map(int, input().split())
l = []
for i in range(m):
    a, b = map(int, input().split())
    l.append((b, a))
l.sort()
answer = 0
last = 0
for b, a in l:
    if a >= last:
        answer += 1
        last = b
print(answer)
### BUGGY CODE ###

# coding: utf-8
#!/usr/bin/env python3

from collections import deque

h, w = map(int, input().split())
a = [ list(input()) for _ in range(h) ]

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False] * w for _ in range(h) ]

q = deque()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.append( (x, y, 0) )
            is_visited[y][x] = True

ans = 0

while q:
    # queue の先頭を取り出す
    x, y, dist = q.popleft()
    ans = max(ans, dist)
    # 4方向にループ
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny:
            continue

        if is_visited[ny][nx]:
            continue

        q.append( (nx, ny, dist+1) )
        is_visited[ny][nx] = True

print(ans)


### FIXED CODE ###

# coding: utf-8
#!/usr/bin/env python3

from collections import deque

# input
h, w = map(int, input().split())
a = [ list(input()) for _ in range(h) ]

# direction vector
dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]

# 訪れたかどうかの情報を持つ bool 値
is_visited = [ [False for _ in range(w)] for __ in range(h) ]

q = deque()

for x in range(w):
    for y in range(h):
        if a[y][x] == "#":
            q.append( (x, y, 0) )
            is_visited[y][x] = True

while q:
    # queue の先頭を取り出す
    x, y, cnt = q.popleft()
    # 4方向にループ
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]

        if nx < 0 or w <= nx or ny < 0 or h <= ny or is_visited[ny][nx]:
            continue

        q.append( (nx, ny, cnt+1) )
        is_visited[ny][nx] = True

print(cnt)
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = sorted(list(map(int,input().split())))
S = []
for x in A:
    for y in B:
        S.append(x+y)
S.sort(reverse = True)
S1 = []
for i in range(min(K,X*Y)):
    for j in range(min(len(C),K)):
        S1.append(S[i]+C[j])
S1.sort(reverse = True)
for i in range(K):
    print(S1[i])

### FIXED CODE ###

from heapq import nlargest

x,y,z,k = map(int,input().split())
A,B,C = [list(map(int,input().split())) for _ in [0]*3]

AB = nlargest(k,[a+b for a in A for b in B])
ABC = nlargest(k,[ab+c for ab in AB for c in C])
print("\n".join(map(str,ABC)))
### BUGGY CODE ###

def primes(n):
  l = [1 for i in range(n+1)]
  l[0] = l[1] = 0
  for i in range(2,int((n)**(1/2))+1):
    if l[i] == 1:
      for j in range(2,(n)//i+1):
        l[i*j] = 0
  return l

l = primes(50000)
while True:
  n = int(input())
  if n == 0:
    break
  count = 0
  for i in range(2,n//2+1):
    if (l[i] and l[n-i]):
      count += 1
  print(count)

### FIXED CODE ###

def primes(n):
  l = [1 for i in range(n+1)]
  l[0] = l[1] = 0
  for i in range(2,int((n)**(1/2))+1):
    if l[i] == 1:
      for j in range(2,n//i+1):
        l[i*j] = 0
  return l

l = primes(50000)
while True:
  n = int(input())
  if n == 0:
    break
  count = 0
  if not(n%2):
    for i in range(3,n//2+1,2):
      if (l[i] and l[n-i]):
        count += 1
    if n == 4:
      count = 1
  else:
    if l[n-2]:
      count += 1
  print(count)
### BUGGY CODE ###

n = int(input())
s = list(input())

m = {'R': [], 'G': [], 'B': []}

for i, c in enumerate(s):
  if c == 'R':
    m['R'].append(i)
  elif c == 'G':
    m['G'].append(i)
  else:
    m['B'].append(i)

result = len(m['R']) * len(m['G']) * len(m['B'])

for i in range(1, n - 1):
  for j in range(i + 1, n):
    k = 2 * j - i

    if k > n or not (s[i - 1] != s[j - 1] and s[j - 1] != s[k - 1] and s[k - 1] != s[i - 1]):
      continue
    result -= 1

print(result)

### FIXED CODE ###

n = int(input())
s = list(input())

m = {'R': 0, 'G': 0, 'B': 0}

for i, c in enumerate(s):
  if c == 'R':
    m['R'] += 1
  elif c == 'G':
    m['G'] += 1
  else:
    m['B'] += 1

result = m['R'] * m['G'] * m['B']

for i in range(1, n - 1):
  for j in range(i + 1, n):
    k = 2 * j - i

    if k > n or not (s[i - 1] != s[j - 1] and s[j - 1] != s[k - 1] and s[k - 1] != s[i - 1]):
      continue
    result -= 1

print(result)
### BUGGY CODE ###

N=list(map(int,input().split()))
A=list(map(int,input().split()))
n=N[0]
k=N[1]
aves=[]
for x in range(n-k+1):
    ave=1
    for i in range(x,k+x):
        ave=ave*A[i]
    aves.append(ave)
for y in range(len(aves)-1):
    if aves[y]<aves[y+1]:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N=list(map(int,input().split()))
A=list(map(int,input().split()))
n=N[0]
k=N[1]
for i in range(n-k):
    if A[i]<A[k+i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(10**9)

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    cnt = Counter(As)

    N2, N3 = (N+1)*(N+1), (N+1)*(N+1)*(N+1)

    def rec(i, j, k):
        z = i*N2 + j*N + k
        expe = memo[z]
        if expe == -1:
            expe = 0.0
            if i > 0:
                expe += i/N * rec(i-1, j, k)
            if j > 0:
                expe += j/N * rec(i+1, j-1, k)
            if k > 0:
                expe += k/N * rec(i, j+1, k-1)
            if i+j+k:
                expe = (expe+1)*N/(i+j+k)
            memo[z] = expe
        return expe

    memo = [-1] * N3

    ans = rec(cnt[1], cnt[2], cnt[3])
    print(ans)


solve()


### FIXED CODE ###

from collections import Counter

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    cnt = Counter(As)

    dp = [[[0.0]*(N+1) for j in range(N+1)] for i in range(N+1)]
    for k in range(N+1):
        for j in range(N+1):
            if j+k > N:
                break
            for i in range(N+1):
                if i+j+k > N:
                    break
                expe = 0.0
                if i > 0:
                    expe += i/N * dp[i-1][j][k]
                if j > 0:
                    expe += j/N * dp[i+1][j-1][k]
                if k > 0:
                    expe += k/N * dp[i][j+1][k-1]
                if i+j+k:
                    expe = (expe+1)*N/(i+j+k)
                dp[i][j][k] = expe

    ans = dp[cnt[1]][cnt[2]][cnt[3]]
    print(ans)


solve()
### BUGGY CODE ###

n = int(input())
def is_multiple_of_nine(x):
    if x < 10:
        if x == 0 or x == 9:
            return True
        else:
            return False
    else:
        running_sum = 0
        while x:
            running_sum += x % 10
            x = x // 10
        return is_multiple_of_nine(running_sum)
    
if is_multiple_of_nine(n):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

import math
n = str(input())
    
running_sum = 0
for i in n:
    if i != "0" and i != "9":
        running_sum += int(i)

if running_sum % 9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import Counter

def comb(n,k):
    nCk = 1
    MOD = 10**9+7

    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= MOD

    for i in range(1,k+1):
        nCk *= pow(i,MOD-2,MOD)
        nCk %= MOD
    return nCk

N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
for i in A:
    ans = 0
    for j in C:
        if i == j:
            ans += comb((C[j] - 1), 2)
        else:
            ans += comb(C[j], 2)
    print(ans)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
x = 0
for i in C:
    x += C[i] * (C[i] - 1) // 2
for a in A:
    print(x - (C[a] - 1))
### BUGGY CODE ###

S = input()
n = len(S)
k = 2019

# Let S = s[0]s[1]....s[n - 1] and
# let A[i] = s[i]s[i+1]...s[n-1] = s[i]*10^(n-i-1) + ... + s[n-1]*10^0
A = [0] * (n + 1) # A[n]はダミー

w = 1
for i in range(n - 1, -1, -1):
    A[i] = (A[i + 1] + w * int(S[i])) % k
    w = w * 10 % k

ans = 0
for j in range(k):
    c = A.count(j)
    ans += c * (c - 1) // 2

print(ans)

### FIXED CODE ###

S = input()
n = len(S)
k = 2019

# Let S = s[0]s[1]....s[n - 1] and
# let A[i] = s[i]s[i+1]...s[n-1] = s[i]*10^(n-i-1) + ... + s[n-1]*10^0
A = [0] * (n + 1) # A[n] = 0
d = {0:1}

w = 1
for i in range(n - 1, -1, -1):
    A[i] = (A[i + 1] + w * int(S[i])) % k
    w = w * 10 % k
    if A[i] in d:
        d[A[i]] += 1
    else:
        d[A[i]] = 1

ans = 0
for j in d:
    ans += d[j] * (d[j] - 1) // 2

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

n = int(input())
a = []
max_list = []
max_i = 0

for i in range(n):
    a.append(str(input()))

a2 = a
for i in set(a2):
    if max_i < a.count(i):
        max_i = a.count(i)

max_list = [x for x in set(a) if a.count(x) == max_i]

max_list.sort()

for i in max_list:
    print(i)       
    

### FIXED CODE ###

import collections

n = int(input())
a = []
max_list = []
max_i = 1

a = [str(input()) for x in range(n)]

c = collections.Counter(a)
c = c.most_common()
max_i = c[0][1]

for i in range(len(c)):
    if max_i == c[i][1]:
        max_list.append(c[i][0])
    else:
        break

max_list.sort()

for i in max_list:
    print(i)
### BUGGY CODE ###

import sys

import numpy as np

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3

memo = np.full(((n+1), (n * max(aa) + 1), 2), -1, dtype=np.int64)
def dfs12(i, c):
    if 0 <= memo[i, c, 0]:
        return memo[i, c]

    if i == n:
        memo[i, c, 0] = 3 if total <= (2 * c) else 0
        memo[i, c, 1] = 3 if total == (2 * c) else 0
        return memo[i, c]

    v0 = dfs12(i + 1, c)
    v1 = dfs12(i + 1, c + aa[i])

    memo[i, c, 0] = (2 * v0[0] + v1[0])
    memo[i, c, 1] = (v0[1] + v1[1])
    return memo[i, c]

a, b = dfs12(0, 0)
ret = (ret - a + b) % 998244353
print(ret)

### FIXED CODE ###

import sys

readInt = lambda: int(sys.stdin.readline())
readIntN = lambda: [int(v) for v in sys.stdin.readline().split(" ")]

total = 0
ret = 1
n = readInt()
aa = []
for i in range(n):
    v = readInt()
    aa.append(v)
    total += v
    ret *= 3


L = (n * max(aa) + 1)
memo = [-1] * ((n+1) * L * 2)
def dfs(i, c):
    key = (i * L * 2) + 2 * c
    if 0 <= memo[key]:
        return memo[key: key+2]

    if i == n:
        memo[key + 0] = 3 if total <= (2 * c) else 0
        memo[key + 1] = 3 if total == (2 * c) else 0
        return memo[key: key + 2]

    v0 = dfs(i + 1, c)
    v1 = dfs(i + 1, c + aa[i])

    memo[key + 0] = (2 * v0[0] + v1[0]) % 998244353
    memo[key + 1] = (v0[1] + v1[1]) % 998244353
    return memo[key: key + 2]

a, b = dfs(0, 0)
ret = (ret - a + b) % 998244353
print(ret)
### BUGGY CODE ###

N = int(input())
s = [list(input()) for _ in range(N)]
l = []
cnt = 0
for st in s:
    st.sort()
    l.append("".join(st))
l.sort()
a = list(set(l))
for uni in a:
    c = l.count(uni)
    if c>1:
        while c>1:
            cnt += c-1
            c -=1
print(cnt)

### FIXED CODE ###

N = int(input())
s = [list(input()) for _ in range(N)]
l = []
for st in s:
    st.sort()
    l.append("".join(st))
l.sort()
cnt = 0
c = 1
for i in range(N-1):
    if l[i]==l[i+1]:
        c += 1
    else:
        if c>1:
            cnt += (1+(c-1))*(c-1)//2
        c = 1
print(cnt+(1+(c-1))*(c-1)//2)
### BUGGY CODE ###

n=int(input())
L=list(map(int,input().split()))
L.sort()
 
count=0
list.sort(L, reverse=True)
 
for i in range(n):
    for j in range(i+1,n):
        for k in range(j+1,n):
            if L[k]>L[i]-L[j]:
                count += 1
 
print(count)


### FIXED CODE ###

import bisect

n=int(input())
L=[int(i) for i in input().split()]

L.sort()

s=0
for i in range(n-1):
      for j in range(i+1,n):
            index=bisect.bisect_left(L,L[i]+L[j])
            s+=index-(j+1)
print(s)
### BUGGY CODE ###

def solve(l,r):
    prime = [True for i in range(r+1)]
    prime[0] = False
    prime[1] = False
    for i in range(2,int(r**0.5)+1):
        for j in range(2*i,r+1,i):
            prime[j] = False
    res = 0
    for i in range(l,r+1,2):
        if prime[i] and prime[(i+1)//2]:
            res += 1
    return res

if __name__ == '__main__':
    q = int(input())
    for i in range(q):
        l,r = map(int,input().split())
        print(solve(l,r))

### FIXED CODE ###

def sieve(n):
    is_prime =[True for i in range(n+1)]
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2,int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i+i,n,i):
                is_prime[j] = False
    c = [0 for i in range(n+1)]
    for i in range(3,n+1,2):
        if is_prime[i] and is_prime[(i+1)//2]:
            c[i] = 1
    for i in range(n):
        c[i+1] += c[i]
    return c

def solve(l,r,c):
    return c[r]-c[l-1]



if __name__ == '__main__':
    q = int(input())
    c = sieve(100000)
    for i in range(q):
        l,r = map(int,input().split())
        print(solve(l,r,c))