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

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

N = int(input())
S = input()
if S[0] == 'W' or S[-1] == 'W':
    print(0)
    exit(0)

Dc = 1
LRsub = 1
Pattern = 1
Sp = S[0]

for i, Sc in enumerate(S):
    if i == 0:
        continue
    if Sc != 'B' and Sc != 'W':
        continue
    Dc = Dc if Sc != Sp else -Dc
    Sp = Sc
    if Dc < 0:
        Pattern *= LRsub
    LRsub += Dc

if LRsub == 0:
    MOD = 10 ** 9 + 7
    for i in range(2,N+1):
        Pattern *= i
        Pattern = Pattern % MOD
    print(Pattern)
else:
    print(0)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7

N = int(input())
S = list(map(lambda x: int(x == "W"),input()))
if S[0] or S[-1]:
    print(0)
    exit(0)

Dc = 1
LRsub = 1
Pattern = 1
Sp = S[0]

for i in range(1,N*2):
    Sc = S[i]
    Dc = Dc if Sc != Sp else -Dc
    Sp = Sc
    if Dc < 0:
        Pattern = (Pattern * LRsub) % MOD
    LRsub += Dc

if LRsub == 0:
    for i in range(2,N+1):
        Pattern = (Pattern * i) % MOD
    print(Pattern)
else:
    print(0)
### BUGGY CODE ###

import numpy as np
from numba import njit

@njit('i8(i8,i4[:,:],i8[:,:],i8)', cache=True)
def solve(N, aff, dpt, MOD):
    for i in range(N):
        row = aff[i]
        for idx in range(N):
            if row[idx] == 1:
                dpt[i+1][(1<<idx):] += dpt[i][:-(1<<idx)]
        dpt[i+1] %= MOD
    return dpt[N][(1<<N)-1]

def main():
    MOD = 10**9 + 7
 
    N = int(input())
    aff = np.array([list(map(int, input().split())) for i in range(N)], dtype='int32')
    dpt = np.zeros((N+1, 1<<N), dtype='int64')
    dpt[0][0] = 1

    print(solve(N, aff, dpt, MOD))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np

MOD = 10**9 + 7
 
N = int(input())
aff = np.array([map(int, input().split()) for i in range(N)])
dpt = np.zeros((N+1, 1<<N), dtype='int64')
dpt[0][0] = 1

for i, row in enumerate(aff):
    for idx, v in enumerate(row):
        if v == 1:
            dpt[i+1][(1<<idx):] += dpt[i][:-(1<<idx)]
    dpt[i+1] %= MOD

print(dpt[N][(1<<N)-1])
### BUGGY CODE ###

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

for i in range(N):
    for j in range(i+1,N) :
        S = S + A[i]*A[j]

ans = S%(10**9+7)

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
K = sum(A)
S = 0

for i in range(N-1):
    K = K - A[i]
    S = S + A[i]*K

ans = S%(10**9+7)

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

import sys
from math import factorial

def solve():
    N, A, B = map(int, input().split())
    v = [int(i) for i in input().split()]

    h1, c1 = half_rekkyo(N, v, 0, N // 2)
    h2, c2 = half_rekkyo(N, v, N // 2, N - N //2)

    max_ave = 0
    cnt = 0

    for i in range(len(h1)):
        for j in range(len(h2)):
            if A <= i + j <= B:
                tot = h1[i] + h2[j]
                ave = tot / (i + j)

                if ave > max_ave:
                    cnt = c1[i] * c2[j]
                    max_ave = ave
                elif ave == max_ave:
                    cnt += c1[i] * c2[j]

    print(max_ave)
    print(cnt)

def half_rekkyo(N, v, s, m):
    max_vs = [0] * (m + 1)
    nums = [0] * (m + 1)

    for cmb in range(2**m):
        # print(bin(cmb))
        value = 0
        cnt = 0

        for i in range(m):
            if cmb & (1 << i):
                value += v[s + i]
                cnt += 1

        # print(value, cnt)

        if value == max_vs[cnt]:
            nums[cnt] += 1
        elif value > max_vs[cnt]:
            nums[cnt] = 1
            max_vs[cnt] = value

    return max_vs, nums

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

if __name__ == '__main__':
    solve()

### FIXED CODE ###

import sys
from math import factorial

def solve():
    N, A, B = map(int, input().split())
    v = [int(i) for i in input().split()]
    v.sort(reverse=True)

    ave_max = sum(v[:A]) / A

    onaji = v.count(v[0])

    if onaji < A:
        k = v[:A].count(v[A - 1])
        n = v.count(v[A - 1])
        cnt = binom(n, k)
    else:
        cnt = 0

        for i in range(A, min(onaji, B) + 1):
            cnt += binom(onaji, i)

    print('{:.8f}'.format(ave_max))
    print(cnt)


def binom(n, k):
    return (factorial(n) // factorial(n - k)) // factorial(k)

def debug(x, table):
    for name, val in table.items():
        if x is val:
            print('DEBUG:{} -> {}'.format(name, val), file=sys.stderr)
            return None

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

import sys
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
sys.setrecursionlimit(10 ** 9)


def main():
    N, M = MAP()
    A = LIST()

    for i in range(M):
        A[A.index(max(A))] //= 2

    print(sum(A))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    N, M = MAP()
    A = LIST()

    minus_A = list(map(lambda x: x*(-1), A))
    heapify(minus_A)
    for i in range(M):
        temp = heappop(minus_A) * (-1)
        heappush(minus_A, temp//2 * (-1))

    print(sum(minus_A) * (-1))


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

obj = input().strip().split(' ')
N, M = map(int, obj)

obj = input().strip().split(' ')
A_list = map(int, obj)

val_list = sorted(A_list, reverse=True)

can_insert = False
for _ in range(M):
    val = val_list.pop(0) // 2
    for i, v in enumerate(val_list):
        if val >= v:
            val_list.insert(i, val)
            can_insert = True
            break
    if not can_insert:
        val_list.append(val)

print(sum(val_list))


### FIXED CODE ###

from heapq import heappush, heappop, heapify

obj = input().strip().split(' ')
N, M = map(int, obj)

obj = input().strip().split(' ')
val_list = [-1 * item for item in list(map(int, obj))]

heapify(val_list)

for _ in range(M):
    val = (-1) * ((heappop(val_list) * (-1)) // 2)
    heappush(val_list, val)

print(-1 * sum(val_list))
### BUGGY CODE ###

s = str(input())
n = len(s)

while '01' in s or '10' in s:
  s = s.replace('01', '')
  s = s.replace('10', '')

print(n-len(s))

### FIXED CODE ###

s = str(input())
print(2*(min(s.count('0'), s.count('1'))))
### BUGGY CODE ###

import sys
n,m=map(int,input().split())
if abs(n-m)>1:
  print(0)
  sys.exit()
cnt=1
for i in range(1,n+1):
  cnt*=i
if n==m:
  print(2*((cnt**2)%((10**9)+7)))
if n-m==1:
  print((cnt*(cnt//n))%((10**9)+7))
if m-n==1:
  print((cnt*cnt*m)%((10**9)+7))


### FIXED CODE ###

import sys
n,m=map(int,input().split())
num=n
mum=m
if 2<=abs(n-m):
  print(0)
  sys.exit()
if abs(n-m)==1:
  while n>1:
    num*=n-1
    n-=1
    num=num%((10**9)+7)
  while m>1:
    mum*=m-1
    m-=1
    mum=mum%((10**9)+7)
  print((num*mum)%((10**9)+7))
  sys.exit()
if abs(n-m)==0:
  while n>1:
    num*=n-1
    n-=1
    num=num%((10**9)+7)
  print((2*(num**2))%((10**9)+7))
  sys.exit()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    R,G,B,N=map(int,input().split())
    cnt=0
    for r in range(N+1):
        for g in range(N+1):
            val=(N-R*r-G*g)/B
            if val==int(val) and val>=0:
                cnt+=1
    print(cnt)

resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    R,G,B,N=map(int,input().split())
    cnt=0
    for r in range(N+1):
        for g in range(N+1):
            val=(N-R*r-G*g)/B
            if val==int(val) and val>=0:
                cnt+=1
    print(cnt)

resolve()
### BUGGY CODE ###

import math
import sys
import bisect
import itertools

N, M = [int(x) for x in input().split()]
MOD = 10 ** 9 + 7

divisor = []
dict = {}

m = M
d = 2
while m != 1:
    while m % d == 0:
        # divisor.append(d)
        m //= d
        dict[d] = dict.get(d, 0) + 1
    d += 1
C = dict.values()
ret = 1


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

def combinations_count(n, r):
    a = max(r, n-r)
    b = min(r, n-r)
    r = 1
    for i in range(a+1, n+1):
        r *= i
    return r // math.factorial(b)


for c in C:
    ret *= combinations_count(c + N - 1, c)
    ret %= MOD

print(ret)


### FIXED CODE ###

import math

N, M = [int(x) for x in input().split()]
MOD = 10 ** 9 + 7

divisor = []
dict = {}

m = M
d = 2
while m != 1:
    while m % d == 0:
        # divisor.append(d)
        m //= d
        dict[d] = dict.get(d, 0) + 1
    d += 1
C = dict.values()
ret = 1


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

def combinations_count(n, r):
    a = max(r, n-r)
    b = min(r, n-r)
    r = 1
    for i in range(a+1, n+1):
        r *= i
    return r // math.factorial(b)


for c in C:
    ret *= combinations_count(c + N - 1, c)
    ret %= MOD

print(ret)
### BUGGY CODE ###

import sys


def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [int(readline()) for _ in range(n)]
    cnt = 0
    while len(a):
        cnt += 1
        t_a = []
        mt = -1
        for i in range(len(a)):
            if mt >= a[i]:
                t_a.append(a[i])
            else:
                mt = a[i]
        a = t_a
    print(cnt)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

import sys
import bisect

def solve():
    readline = sys.stdin.buffer.readline
    mod = 10 ** 9 + 7
    n = int(readline())
    a = [int(readline()) for _ in range(n)]
    res = []
    for i in range(n-1, -1, -1):
        p = bisect.bisect_right(res, a[i])
        if len(res) == p:
            res.append(a[i])
        else:
            res[p] = a[i]
    print(len(res))


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

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()
S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]
for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = np.array([[mod,mod,mod] for i in range(N)])

# print(routes)
# def skip(now,move_cnt):
#     flag = True
#     if used[now] != mod:
#         if used[now] % 3 == 0 and move_cnt > used[now]:
#             flag = False
#     if used[now] > move_cnt:
#         if used[now] % 3 == 0 and move_cnt % 3 != 0:
#             pass
#         else:
#             used[now] = move_cnt
#     if flag:
#         for route in routes[now]:
#             skip(route,move_cnt+1)
def move2next(now,move_cnt):
    flag = True
    if used[now, move_cnt % 3] == mod:
        used[now, move_cnt % 3] = move_cnt
    elif used[now, move_cnt % 3] <= move_cnt:
        flag = False # この条件だと前より遅いので探索ストップ
    else:
        used[now, move_cnt % 3] = move_cnt
    if flag:
        for route in routes[now]:
            move2next(route, move_cnt+1)

move2next(S,0)
# print(used)
try:
    ans = used[T, 0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import numpy as np
import queue

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))
N,M = LI()

um = [[] for i in range(M)]
for i in range(M):
    um[i] = LI()

S,T = LI()
S -= 1
T -= 1
routes = [[] for i in range(N)]

for i in range(M):
    u,m = um[i]
    u -= 1
    m -= 1
    routes[u].append(m)

used = [[mod,mod,mod] for i in range(N)]

from collections import deque

# q = queue.Queue()
q = deque()
q.append((S,0))
# Deep First Serch
while q:
    now, cost = q.popleft()
    for route in routes[now]:
        n_state = (cost + 1) % 3
        if used[route][n_state] == mod:
            used[route][n_state] = cost + 1
            q.append((route,cost+1))


# print(used)
try:
    ans = used[T][0]
    if ans == mod:
        ans = -1
    else:
        ans = ans/3
except:
    ans = -1
print(int(ans))
### BUGGY CODE ###

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

lis = list()
for i in range(1, N+1):
    lis.append(A.index(i)+1)

L=[str(a) for a in lis]
L=" ".join(L)
print(L)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
L = [0]*N
for i in range(0, N):
    L[A[i]-1] = i + 1
print(*L)
### BUGGY CODE ###

n = int(input())
t,a = map(int,input().split())
for i in range(n-1):
  T,A=map(int,input().split())
  count = 0
  while (A*count < a) or (T*count < t):
    count += 1
  a = count * A
  t = count * T
print(a+t)

### FIXED CODE ###

n = int(input())
t,a = map(int,input().split())
for i in range(n-1):
  T,A=map(int,input().split())
  count = max(a//A,t//T)
  while (A*count < a) or (T*count < t):
    count += 1
  a = count * A
  t = count * T
print(a+t)
### BUGGY CODE ###

from collections import deque
p = list(map(int,input().split()))
Q = deque()
Q.append(p)
cnt = 0
while Q:
  temp = Q.popleft()
  x,y = temp
  s = [x-1,y-2]
  t = [x-2,y-1]
  if x-1>=2 or y-2>=2:
    Q.append(s)
  if x-2>=2 or y-1>=2:
    Q.append(t)
  if s==[0,0] or t==[0,0]:
    cnt += 1
print(cnt)

### FIXED CODE ###

x,y = map(int,input().split())
mod = 10**9+7
def comb(a,b):
  comb = 1
  chld = 1
  for i in range(b):
    comb = comb*(a-i)%mod
    chld = chld*(b-i)%mod
  return (comb*pow(chld,mod-2,mod))%mod
if (x+y)%3!=0:
  print(0)
else:
  nm = (x+y)//3
  n = y-nm
  m = x-nm
  if n>=0 and m>=0:
    print(comb(n+m,m))
  else:
    print(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
a = []
count = 0
for i in range(N):
    a += [''.join(sorted(input()))]
for i in range(N-1):
    for j in range(1, N):
        if i+j >= N:
            break
        if a[i] == a[i+j]:
            count += 1
print(count)

### FIXED CODE ###

from collections import defaultdict

n = int(input())
s = [input() for _ in range(n)]

d = defaultdict(int)
for i in range(n):
    d["".join(sorted(s[i]))] += 1

ans = 0
for k in d.keys():
    ans += d[k] * (d[k]-1) // 2
print(ans)
### BUGGY CODE ###

T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]
    S = input()
    dp = set([0])
    for a, s in zip(A[::-1], S[::-1]):
        if s == '1':
            dp = dp if a in dp else set()
        else:
            for b in dp.copy():
                dp.add(b ^ a)
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')


### FIXED CODE ###

T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    A = [int(_) for _ in input().split()]
    S = input()
    dp = set([0])
    for a, s in zip(A[::-1], S[::-1]):
        for b in dp:
            a = min(a, a ^ b)
        if s == '1':
            if a:
                dp = set()
                break
        else:
            dp2 = set([a])
            for b in dp:
                dp2.add(min(b, a ^ b))
            dp = dp2
    ans += [0 if 0 in dp else 1]
print(*ans, sep='\n')
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
dp = [float('inf')]*len(a)
dp[0] = 0
for i in range(len(a)):
    for j in range(1, k+1):
        if i+j < len(a):
            dp[i+j] = min(dp[i+j], dp[i] + abs(a[i+j] - a[i]))
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
dp = [float('inf')]*len(a)
dp[0] = 0
for i in range(len(a)):
    for j in range(i+1, min(i+k+1, len(a))):
        dp[j] = min(dp[j], dp[i] + abs(a[j] - a[i]))
print(dp[-1])
### BUGGY CODE ###

import itertools

n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18


costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))


x_dir = [[INF] * n for i in range(1 << n)]
y_dir = [[INF] * n for i in range(1 << n)]

for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state][i] = min(costs[i], x_dir[bit_state][i])
        y_dir[bit_state][i] = min(costs[i], y_dir[bit_state][i])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state][j] = min(x_dir[bit_state][j], c * abs(yi - yj))
            y_dir[bit_state][j] = min(y_dir[bit_state][j], c * abs(xi - xj))


ans = [INF] * (n + 1)
for state in itertools.product((0, 1, 2), repeat=n):
    x_bit = 0
    y_bit = 0
    cnt = 0
    for i in range(n):
        if state[i] == 1:
            x_bit |= (1 << i)
            cnt += 1
        elif state[i] == 2:
            y_bit |= (1 << i)
            cnt += 1
    tmp = 0
    for i in range(n):
        tmp += min(x_dir[x_bit][i], y_dir[y_bit][i])
    ans[cnt] = min(ans[cnt], tmp)

for res in ans:
    print(res)

### FIXED CODE ###

#import random


n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 13

#n = 15
#info = []
#for i in range(n):
#    info.append([random.randint(-10000, 10000), random.randint(-10000, 10000), random.randint(1, 1000000)])


costs = [INF] * n
for i, (x, y, c) in enumerate(info):
    costs[i] = c * min(abs(x), abs(y))

OFFSET = n
x_dir = [INF] * ((1 << n) * OFFSET)
y_dir = [INF] * ((1 << n) * OFFSET)


for bit_state in range(1 << n):
    for i, (xi, yi, c) in enumerate(info):
        x_dir[bit_state * OFFSET + i] = min(costs[i], x_dir[bit_state * OFFSET + i])
        y_dir[bit_state * OFFSET + i] = min(costs[i], y_dir[bit_state * OFFSET + i])
        if not((bit_state >> i) & 1):
            continue
        for j, (xj, yj, c) in enumerate(info):
            x_dir[bit_state * OFFSET + j] = min(x_dir[bit_state * OFFSET + j], c * abs(yi - yj))
            y_dir[bit_state * OFFSET + j] = min(y_dir[bit_state * OFFSET + j], c * abs(xi - xj))


ans = [INF] * (n + 1)
for bit_state in range((1 << n) - 1):
    x_bit = bit_state
    cnt = bin(bit_state).count("1")
    while x_bit >= 0:
        x_bit &= bit_state
        # bit_stateの下位集合sub_stateの列挙
        # 処理はじめ
        y_bit = bit_state - x_bit
        tmp = 0
        for i in range(n):
            tmp += min(x_dir[x_bit * OFFSET + i], y_dir[y_bit * OFFSET + i])
        ans[cnt] = min(ans[cnt], tmp)
        # 処理おわり
        x_bit -= 1

ans[-1] = 0
for res in ans:
    print(res)
### BUGGY CODE ###

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

t = 1
for i in range(K):# A[0] ~ A[K-1]
  t *= A[i]
  
for i in range(K, N):
  temp = t // A[i-K] * A[i]
  if t < temp:
    print('Yes')
  else:
    print('No')
  t = temp

### FIXED CODE ###

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

for i in range(K, N):
  if A[i-K] < A[i]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools

def main():
    n = int(input())
    s = input()
    l = list(itertools.combinations(list(range(n)),3))
    a = set()
    for i in l:
        k = s[i[0]]+s[i[1]]+s[i[2]]
        a.add(k)
    print(len(a))

if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd
INF = float("inf")

import sys
input=sys.stdin.readline
import itertools

def main():
    n = int(input())
    s = input()

    ans = 0
    for i in range(10):
        a = s.find(str(i))
        if a == -1:
            continue
        for j in range(10):
            b = s.find(str(j),a+1)
            if b == -1:
                continue
            for k in range(10):
                c = s.find(str(k),b+1)
                if c == -1:
                    continue
                else:
                    ans += 1
    print(ans)

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

import math
Q = int(input())
lr = [list(map(int, input().split())) for i in range(Q)]

max_l = max(lr, key=lambda x:x[1])[1]

a = list(range(2,int(math.ceil(max_l**0.5)+1)))
prime = list(range(2,max_l+1))
i = 1
while True:
    b = filter(lambda x: x%a[i-1] != 0,a[i:])
    a = a[:i]
    a.extend(b)
    i += 1
    if i > len(a):
        break

for i in range(len(a)):
    prime = list(filter(lambda x: x%a[i] != 0 or x == a[i],prime))

like2017 = []
for i in prime:
    if (i+1)/2 in prime:
        like2017.append(i)

for i in range(Q):
    print(len(list(filter(lambda x: lr[i][0] <= x <= lr[i][1],like2017))))


### FIXED CODE ###

import math
Q = int(input())
lr = [list(map(int, input().split())) for i in range(Q)]

max_l = max(lr, key=lambda x:x[1])[1]

prime = list(range(2,int(math.ceil(max_l**0.5)+1)))

m = 1
while True:
    b = filter(lambda x: x%prime[m-1] != 0,prime[m:])
    prime = prime[:m]
    prime.extend(b)
    m += 1
    if m > len(prime):
        break

like2017 = {-1:0,1:0}
for i in range(3,max_l+2,2):
    k = 0
    for j in prime:
        if (i%j == 0 or ((i+1)/2)%j == 0) and i != j and (i+1)/2 != j:
            k += 1
            break
    if k == 0:
        like2017[i] = like2017[i-2] + 1
    else:
        like2017[i] = like2017[i-2]


for i in range(Q):
    print(like2017[lr[i][1]]-like2017[lr[i][0]-2])
### BUGGY CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

n=0
m=0
ans=-inf
l=[]

def dfs(s):
  global n
  global m
  global ans
  global l

  if len(s)==n:
    _ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if int(s[b])-int(s[a])==c:
        _ans+=d
    ans=max(ans,_ans)

  if len(s)!=n:
    x=int(s[-1])
    for i in range(x,m+1):
      dfs(s+str(i))

def main():
  global n
  global m
  global ans
  global l

  n,m,q=LI()
  l=[LI() for _ in range(q)]

  for i in range(1,m+1):
    dfs(str(i))

  return ans

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

n=0
m=0
ans=-inf
l=[]

def dfs(s):
  global n
  global m
  global ans
  global l

  if len(s)==n:
    _ans=0
    for a,b,c,d in l:
      a-=1
      b-=1
      if s[b]-s[a]==c:
        _ans+=d
    ans=max(ans,_ans)

  if len(s)!=n:
    x=s[-1]
    for i in range(x,m+1):
      dfs(s+[i])

def main():
  global n
  global m
  global ans
  global l

  n,m,q=LI()
  l=[LI() for _ in range(q)]

  for i in range(1,m+1):
    dfs([i])

  return ans

# main()
print(main())