Harryxun/stf_run huggingface dataset:
n = int(input())
a = list(map(int, input().split()))

a = sorted(set(a))
w = 0
h = 0
while True:
    h = 1
    while True:
        if w + h == len(a):
            print(a)
            break
        if a[w+h] % a[w] == 0:
            print(h)
            del a[w+h]
        else:
            print(a[w+h], h, w, a)
            h += 1
    w += 1
    if w == len(a):
        print(len(a))
        exit()

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
c = Counter(a)
prime = [True] * (10 ** 6 + 10)

b = sorted(set(a))

for i in b:
    num = i * 2
    while True:
        if num >= 10 ** 6 + 1:
            break
        prime[num] = False
        num += i

ans = 0
for s in a:
    if prime[s] == True and c[s] == 1:
        ans += 1

print(ans)
n = int(input())
x = input()
xx = int(x, 2)
value = [0, 1]
count_1 = x.count('1')
for i in range(2, 2 * (10 ** 5) + 1):
    ans = 1
    i = i % bin(i).count('1')
    value.append(ans + value[i])

for i in range(n):
    print(int(t, 2))

### FIXED CODE ###

n = int(input())
x = input()
count_1 = x.count('1')
value = [0, 0]
x_int = int(x, 2)
value[0] = x_int % (count_1 - 1) if count_1 > 1 else 0
value[1] = x_int % (count_1 + 1)
for i in range(n):
    if x[i] == '0':
        tmp = (pow(2, n - i - 1, count_1 + 1) + value[1]) % (count_1 + 1)
    else:
        if count_1 == 1:
            print(0)
            continue
        tmp = (-pow(2, n - i - 1, count_1 - 1) + value[0]) % (count_1 - 1)
    ans = 1
    while tmp > 0:
        tmp = tmp % (bin(tmp).count('1'))
        ans += 1
    print(ans)
#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
n = int(input())
s = [input()for _ in range(n)]
ac = 0
wa = 0
tle = 0
re = 0

for i in s:
    if i == "AC":
        ac += 1
    elif i == "WA":
        wa += 1
    elif i == "TLE":
        tle += 1
    else:
        re += 1

print("AC" + " x", end = "")
print( ac)
print("WA" + " x", end = "")
print( wa)
print("TLE" + " x", end = "")
print( tle)
print("RE" + " x", end = "")
print( re)
#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
n = int(input())
s = [input()for _ in range(n)]
ac = 0
wa = 0
tle = 0
re = 0

for i in s:
    if i == "AC":
        ac += 1
    elif i == "WA":
        wa += 1
    elif i == "TLE":
        tle += 1
    else:
        re += 1

print("AC" + " x", end = "")
print( ac)
print("WA" + " x", end = "")
print( wa)
print("TLE" + " x", end = "")
print( tle)
print("RE" + " x", end = "")
print( re)


### FIXED CODE ###

#n, m, q = map(int, input().split())
#List = list(map(int, input().split()))
#req = [list(map(int, input().split())) for _ in range(q)]
#t = t[:-1]
#print(ans[j], end = "") 改行無しで出力
#[0]*n
n = int(input())
s = [input()for _ in range(n)]
ac = 0
wa = 0
tle = 0
re = 0

for i in s:
    if i == "AC":
        ac += 1
    elif i == "WA":
        wa += 1
    elif i == "TLE":
        tle += 1
    else:
        re += 1

print("AC" + " x ", end = "")
print( ac)
print("WA" + " x ", end = "")
print( wa)
print("TLE" + " x ", end = "")
print( tle)
print("RE" + " x ", end = "")
print( re)
n,m = map( int, input().split())
  input_list = [[] for i in range(n)]

for i in range(m):
  p,y = map(int, input().split())
  input_list[p-1].append((y,i))
  
for i in input_list :
  i.sort()

result = [None]*m

for p,i in enumerate(input_list) :
  for n, (a,b) in enumerate(i):
    result[b] = str(p+1).zfill(6)+str(n+1).zfill(6)
    
print(*result, sep = '\n')

### FIXED CODE ###

n,m = map( int, input().split())
  
result= {}
input_list = [[] for i in range(n)]


for i in range(m):
  p,y = map(int, input().split())
  input_list[p-1].append((y,i))
  
for i in input_list :
  i.sort()

result = [None]*m

for p,i in enumerate(input_list) :
  for n, (a,b) in enumerate(i):
    result[b] = str(p+1).zfill(6)+str(n+1).zfill(6)
    
print(*result, sep = '\n')
n,w = map(int,input().split())
v = [list(map(int,input().split())) for _ in range(n)]
dp = [[0]*(w+1) for _ in range(n+1)]
for i in range(1,n+1):
  for j in range(w+1):
    if j < v[i-1][0]:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-v[i-1][0]]+v[i-1][1])
print(dp[n][w])

### FIXED CODE ###

N = int(input())
h = list(map(int,input().split()))
h = [0] + h
dp = [0]*(N+1)
dp[2] = abs(h[2]-h[1])
for i in range(3,N+1):
  dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[N])
N = int(input())
a = 0
l = []

for i in range(1,12):
    a += 26**i
    l.append(a)

al = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

ans = []

while N != 0:
    x = N % 26
    N = N // 26
    ans.append(x)

ans.reverse()
ans_2 = []

for i in ans:
    if i == 0:
        ans_2.append(al[26])
    else:
        ans_2.append(al[i-1])

print("".join(ans_2))


### FIXED CODE ###

import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n = k() - 1
i = 1
s = 26

while n >= s:
    n -= s
    s *= 26
    i += 1

lst = []
for j in range(i):
    lst.append(n % 26)
    n //= 26

for j in lst[::-1]:
    print(chr(j + ord('a')), end='')
import numpy as np

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

print(*np.argsort(A)+1)

### FIXED CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
tmp = np.argsort(A)+1
print(*tmp)
S = input()
K = input()
count = 0
for i in range(len(S)):
    if S[i]=="1":
        count+=1
    else:
        break
        
print(1) if K <= count else print(S[count])


### FIXED CODE ###

S = input()
K = input()
count = 0
for i in range(len(S)):
    if S[i]=="1":
        count+=1
    else:
        break
        
print(1) if int(K) <= count else print(S[count])
n = int(input())
cards = {} #空の辞書
for i in range(n):
    card = input()
    cards[card] = 1
    
#print(cards)

for c in ['S', 'H', 'C', 'D']:
    for n in range(1,13):
        card = c + ' ' + str(n)
        if not key in cards:
            print(key)


### FIXED CODE ###

n = int(input())
cards = {} #空の辞書
for i in range(n):
    card = input()
    cards[card] = 1
    
#print(cards)

for c in ['S', 'H', 'C', 'D']:
    for n in range(1,14):
        key = c + ' ' + str(n)
        if not key in cards:
            print(key)
N, Q = map(int, input().split())

v = [[] for i in range(N)]
score = [0]*N

def dfs(p):
  for i in v[p-1]:
    if p < i:
      score[i-1] += score[p-1]
      dfs(i)
      
for i in range(N-1):
  a, b = map(int, input().split())
  v[a-1].append(b)
  v[b-1].append(a)

for j in range(Q):
  p, x = map(int, input().split())
  score[p-1] += x

dfs(1)
score_int=[str(a) for a in score]
output= ' '.join(score_int)
print(output)
  

### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion

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

v = [[] for i in range(N)]
score = [0]*N

def dfs(cur,par):
  for chi in v[cur]:
    if chi == par:
      continue
    score[chi] += score[cur]
    dfs(chi, cur)
      
for i in range(N-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  v[a].append(b)
  v[b].append(a)

for j in range(Q):
  p, x = map(int, input().split())
  score[p-1] += x

dfs(0,-1)
score_int=[str(a) for a in score]
output= ' '.join(score_int)
print(output)
list(input())
t=list(input())
a=[0]*27
for i in range(len(s)):
  if a[ord(s[i])-96]==0:
    a[ord(s[i])-96]=ord(t[i])-96
  elif a[ord(s[i])-96]==ord(t[i])-96:
    continue
  else:
    print("No")
    exit()
print("Yes")


### FIXED CODE ###

a=list(input())
b=list(input())
from collections import Counter
def f(s):
    return sorted(Counter(s).values())
if f(a)==f(b):
    print("Yes")
else:
    print("No")
combNum = [0]*100
resultNum = 0
while True:
    calcResult = 0
    numList1 = list(range(1,n+1,1))
    numList2 = list(range(1,n+1,1))
    numList3 = list(range(1,n+1,1))
    n,x = map(int, input().split())
    if n is x is 0:
        break
    else:
        for index1 in range(n):
            for index2 in range(n):
                for index3 in range(n):
                    #index = [numList1[index1], numList2[index2], numList3[index3]]
                    if numList1[index1] is numList2[index2] or numList1[index1] is numList3[index3] or numList2[index2] is numList3[index3] or numList1[index1] is numList2[index2] is numList3[index3]:
                    #if index.count(numList1[index1])>1 or index.count(numList1[index2])>1 or index.count(numList1[index3])>1:
                        pass                
                    else:
                        if numList1[index1]<numList2[index2]<numList3[index3]:
                            calcResult = numList1[index1] + numList2[index2]+numList3[index3]
                            if calcResult == x:
                                combNum[inNum] =combNum+1
                                resultNum +=1
                        else:
                            pass
for index in range(resultNum):
    print(combNum[index])


### FIXED CODE ###

dataNum = 0
combNum = [0] * 100
while True:
    n,x=map(int, input().split())
    if n is x is 0:
        break
    else:
        for a in range(1,n-1):
            for b in range(a+1,n):
                for c in range(b+1,n+1):
                    calcResult = a + b + c
                    if calcResult == x:
                        combNum[dataNum] += 1
                    else:
                        pass
    dataNum += 1

for index in range(dataNum):
    print(combNum[index])
a=int(input())
b=list(input())
b.upper()
c=0
for i in range(a):
  if b[i]=='A':
    if b[i]+b[i+1]+b[i+2]=='ABC':
      c+=1
  else:
    pass
print(c)    


### FIXED CODE ###

n=int(input())
s=list(input())
d=0
for i in range(n):
  if n-(i+1)>=2:
    if s[i]=='A' and s[i+1]=='B' and s[i+2]=='C':
      d+=1
  else:
    pass
print(d)
swithCount, lightCount = map(int, input().split())
swithList = [0] * lightCount

for i in range(swithCount):
    connectedLightList = list(map(int, input().split()))
    for lightIndex in connectedLightList[1:]:
        lightIndex -= 1
        swithList[i] = swithList[i] | 1 << lightIndex

expectedLightStatusList = list(map(int, input().split()))
expectedLightStatus = 0

for i, eachStatus in enumerate(expectedLightStatusList):
    expectedLightStatus = expectedLightStatus | eachStatus << i

resultCount = 0
for eachSwitchSet in range(1 << swithCount):
    actuallyLightStatus = 0
    for switchIndex in range(swithCount):
        if eachSwitchSet >> switchIndex & 1:
            actuallyLightStatus = actuallyLightStatus ^ swithList[switchIndex]

    if expectedLightStatus == actuallyLightStatus:
        resultCount += 1

print(resultCount)


### FIXED CODE ###

swithCount, lightCount = map(int, input().split())
swithList = [0] * swithCount

for lightIndex in range(lightCount):
    connectedSwitchList = list(map(int, input().split()))
    for si in connectedSwitchList[1:]:
        switchIndex =  si - 1
        swithList[switchIndex] = swithList[switchIndex] | 1 << lightIndex

expectedLightStatusList = list(map(int, input().split()))
expectedLightStatus = 0

for i, eachStatus in enumerate(expectedLightStatusList):
    expectedLightStatus = expectedLightStatus | eachStatus << i

resultCount = 0
for eachSwitchSet in range(1 << swithCount):
    actuallyLightStatus = 0
    for switchIndex in range(swithCount):
        if eachSwitchSet >> switchIndex & 1:
            actuallyLightStatus = actuallyLightStatus ^ swithList[switchIndex]

    if expectedLightStatus == actuallyLightStatus:
        resultCount += 1

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

a=[]
for i in range(n):
    a[i] = list(map(int,input().split()))

b=[]
for i in range(m):
    b.append(int(input()))
    
for i in range(n):
    c = 0
    for j in range(m):
        c += a[i][j]*b[j]
    print(c)

### FIXED CODE ###

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

a = [[0 for i in range(m)] for j in range(n)]

for i in range(n):
    a_tmp = list(map(int,input().split()))
    for j in range(m):
        a[i][j] = a_tmp[j]

b=[]
for i in range(m):
    b.append(int(input()))
    
for i in range(n):
    c = 0
    for j in range(m):
        c += a[i][j]*b[j]
    print(c)
w,h = list(map(int, input().split()))
print("#"*(w+2))
for i in range(h):
  print("#", input(), "#", sep="")
print("#"*(w+2))

### FIXED CODE ###

h,w = list(map(int, input().split()))
print("#"*(w+2))
for i in range(h):
  print("#", input(), "#", sep="")
print("#"*(w+2))
N, M = map(int, input().split())		# 5 7

h=[]
for i in range(N+1):
	h.append([])

a=[]
b=[]

for i in range(M):
	A, B = map(int, input().split())		# 5 7
	h[A].append(B)
	h[B].append(A)
	a.append(A)
	b.append(B)



def dfs(Graph, Start, Visited=None):
	if(Visited==None): Visited = []
	Visited.append(Start)
	#print(Start, Visited)
	for Next in Graph[Start]:
		if( Next in Visited ): 
			#print("   Visited", Next, Visited)
			continue
		dfs(Graph, Next, Visited)

z=[_ for _ in range(1, N+1)]
#print(z)
ans=0

import copy
for i in range(N):
	g = copy.deepcopy(h)
	
	A = a[i]
	B = b[i]
	n = i+1

	g[A].remove(B)
	g[B].remove(A)
	
	Visited = []
	dfs(g, n, Visited)
	
	#print(Visited)
	if len( list(set(z) - set(Visited)) ) > 0:
	    ans += 1

	
print(ans)


### FIXED CODE ###

N, M = map(int, input().split())		# 5 7

h=[]
for i in range(N+1):
	h.append([])

a=[]
b=[]

for i in range(M):
	A, B = map(int, input().split())		# 5 7
	h[A].append(B)
	h[B].append(A)
	a.append(A)
	b.append(B)




def dfs(Graph, Start, Visited=None):
	if(Visited==None): Visited = []
	Visited.append(Start)
	#print(Start, Visited)
	for Next in Graph[Start]:
		if( Next in Visited ): 
			#print("   Visited", Next, Visited)
			continue
		dfs(Graph, Next, Visited)

z=[_ for _ in range(1, N+1)]
#print(z)
ans=0

import copy
for i in range(M):
	g = copy.deepcopy(h)
	
	A = a[i]
	B = b[i]

	g[A].remove(B)
	g[B].remove(A)
	
	Visited = []
	dfs(g, 1, Visited)
	
	#print(A, B, i, Visited)
	if len( list(set(z) - set(Visited)) ) > 0:
	    ans += 1

	
print(ans)
S = input()

len = 0

ans = []
for ch in S:
    if ch in 'ACGT':
        len = len +1
    else:
        ans.append(len)
        len = 0
        
if len(ans) == 0:
    print(0)
else:
    max(ans)

### FIXED CODE ###

S = input()
ACGT = ["A","C","G","T"]

ans = 0 
ans_lis = [0]

for i in range(len(S)):
    if S[i] in ACGT:
        ans = ans + 1 
        if i == (len(S)-1):
            ans_lis.append(ans)
    elif S[i] not in ACGT:
        ans_lis.append(ans)
        ans = 0 

print(max(ans_lis))
sus = 0

for i in a:
    su = su - i
    sus = sus + i * su

"""comb = len(a) * (len(a) - 1) / 2
comb = int(comb)

sum = 0
la = len(a)

for i in range(comb):
    #print(a)
    for j in range(1, la):
        #print(a[i])
        sum = sum + a[0] * a[i]
    a = a[1:]
    la = la - 1
    #print(a)"""

print(sus % (10**9 + 7))

### FIXED CODE ###

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

su = sum(a)
sus = 0

for i in a:
    su = su - i
    sus = sus + i * su

print(sus % (10**9 + 7))
N = int(input())
List = [int(j) for j in input().split(" ")]
Sum = 0
for n in range(0,N-1):
  for m in range(n+1,N):
    Sum += List[i]*List[j]
print(Sum)

### FIXED CODE ###

N = int(input())
List = [int(j) for j in input().split(" ")]
Sum = 0
for n in range(0,N-1):
  for m in range(n+1,N):
    Sum += List[n]*List[m]
print(Sum)
n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
l = [x[i]-x[i-1] for i in range(1,m)]
l.sort(reverse=True)
ans = x[m-1] - x[0]
if len(x) == 1:
    print(ans)
else:
    for i in range(n-1):
        ans -= l[i]
    print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
x = list(map(int, input().split()))
x.sort()
l = [x[i]-x[i-1] for i in range(1,m)]
l.sort(reverse=True)
ans = x[m-1] - x[0]
if n >= m:
    print(0)
else:
    for i in range(n-1):
        ans -= l[i]
    print(ans)
n,a,b = map(int,input().split())
if a > b:
    print(0)
elif a == b:
    print(1)
else:
    print((n - 2) * (b - a) + 1))

### FIXED CODE ###

n,a,b = map(int,input().split())
print(max(0,(n - 2) * (b - a) + 1))
import numpy as np
n, k = map(int,input().split())
a = list(map(int,input().split()))
start = [i for i,x in enumerate(a) if x == min(a)]
m = 10000000
for i in start:
    if np.ceil(i/(k-1))+np.ceil(((n-1)-i)/(k-1)) < m:
        m = np.ceil(i/(k-1))+np.ceil(((n-1)-i)/(k-1))
print(m)

### FIXED CODE ###

s = input()
print(s.count("+")-s.count("-"))
n = int(input())
l = list(map(int, input().split(" ")))
a =[0]*num

for i in range(n):
    #print(i)
    a[l[i]-1] = i + 1 #each_numのi番目のインデックスに代入, -1 はi 番目が1,2,3 ...

for i in range(n):
    print(a[i], end = " ")

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split(" ")))
a =[0]*n

for i in range(n):
    #print(i)
    a[l[i]-1] = i + 1 #each_numのi番目のインデックスに代入, -1 はi 番目が1,2,3 ...

for i in range(n):
    print(a[i], end = " ")
N=int(input())
a=[list(map(int,input().split())) for i in range(N)]
flag=False
H=0
for cx in range(101):
    if flag:
        break
    for cy in range(101):
        if flag:
            break
        for i in range(N):
            if a[i][2]!=0:
                if H==0:
                    H=a[i][2]+abs(cx-a[i][0])+abs(cy-a[i][1])
                if H!=a[i][2]+abs(cx-a[i][0])+abs(cy-a[i][1]):
                    break
            if i==N-1:
                x=cx
                y=cy
                flag=True
                for k in range(N):
                    if a[k][2]!=max(H-abs(x-a[k][0])-abs(y-a[k][1]),0):
                        flag=False
print(x,y,H)

### FIXED CODE ###

N=int(input())
a=[list(map(int,input().split())) for i in range(N)]
flag=False
for cx in range(101):
    if flag:
        break
    for cy in range(101):
        count=0
        if flag:
            break
        for i in range(N):
            if a[i][2]!=0:
                if count==0:
                    H=a[i][2]+abs(cx-a[i][0])+abs(cy-a[i][1])
                    count+=1
                if H!=a[i][2]+abs(cx-a[i][0])+abs(cy-a[i][1]):
                    break
            if i==N-1:
                x=cx
                y=cy
                flag=True
                for k in range(N):
                    if a[k][2]!=max(H-abs(x-a[k][0])-abs(y-a[k][1]),0):
                        flag=False
print(x,y,H)
n = int(input())
a, b, c, d = 0, 0, 0, 0
for i in range(n):
  s = input()
  if s == 'AC':
    a+=1
  elif s== 'WA':
    b+=1
  elif s=='TLE':
    c+=1
  else:
    d+=1
print("AC x "a)
print("WA x "b)
print("TLE x "c)
print("RE x "d)

### FIXED CODE ###

n = int(input())
a, b, c, d = 0, 0, 0, 0
for i in range(n):
  s = input()
  if s == 'AC':
    a+=1
  elif s== 'WA':
    b+=1
  elif s=='TLE':
    c+=1
  else:
    d+=1
print("AC x {}".format(a))
print("WA x {}".format(b))
print("TLE x {}".format(c))
print("RE x {}".format(d))
H,W,M=map(int,input().split())
R=[list(map(int,input().split())) for i in range(M)]

listH=[]
for i in range(M):
  listH.append(0)

listW=[]
for i in range(M):
  listW.append(0)
  
for i in range(M):
  listH[R[i-1][0]-1]+=1
maxH=0
listHmax=[]
jH=0
for i in range(M):
  if listH[i]==max(maxH,listH[i]):
    maxH=listH[i]
    listHmax.append(i)
    jH+=1

for i in range(M):
  listW[R[i-1][1]-1]+=1
maxW=0
listWmax=[]
jW=0
for i in range(M):
  if listW[i]==max(maxW,listW[i]):
    maxW=listW[i]
    listWmax.append(i)
    jW+=1
print (maxW+maxH)

### FIXED CODE ###

H,W,M=map(int,input().split())
R=[list(map(int,input().split())) for i in range(M)]
import sys
listH=[]
for i in range(H):
  listH.append(0)
for i in range(M):
  listH[R[i][0]-1]+=1
maxH=0
listHmax=[]
jH=0
for i in range(H):
  if listH[i]>maxH:
    maxH=listH[i]
    listHmax=[]
    listHmax.append(i)
    jH=1
  elif listH[i]==maxH:
    listHmax.append(i)
    jH+=1

listW=[]
for i in range(W):
  listW.append(0)
for i in range(M):
  listW[R[i][1]-1]+=1
maxW=0
listWmax=[]
jW=0
for i in range(W):
  if listW[i]>maxW:
    maxW=listW[i]
    listWmax=[]
    listWmax.append(i)
    jW=1
  elif listW[i]==maxW:
    listWmax.append(i)
    jW+=1

T=0
for i in range(M):
  if (listH[R[i][0]-1]==maxH and listW[R[i][1]-1]==maxW):
    T+=1
  else:
    continue
if T==jH*jW:
  print (maxH+maxW-1)
else:
  print (maxH+maxW)
import sys
input = sys.stdin.readline
q = int(input())

p=1000003

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % p
    elif y % 2 == 0 : return power(x, y//2)**2 % p
    else            : return power(x, y//2)**2 * x % p
    
factorial_list=[1 for i in range(p)]
for i in range(1,p):
    factorial_list[i]=factorial_list[i-1]*i%p
    
inv_list=[1 for i in range(p)]
inv_list[-1]=factorial_list[-1]
for i in range(p-1,1,-1):
    inv_list[i-1]=inv_list[i]*i%p
    
for i in range(q):
    x,d,n=(int(i) for i in input().split())
    if d%p==0:
        ans=power(x,n)
        print(ans%p)
    elif x<=p*d<=x+(n-1)*d or x==0:
        print(0)
    else:
        x=x*power(d,p-2)%p
        ans=factorial_list[x+n-1]*inv_list[x-1]*power(d,n)
        print(ans%p)
        


### FIXED CODE ###

import sys
input = sys.stdin.readline
q = int(input())

p=1000003

flist=[1 for i in range(p)]
for i in range(1,p):
    flist[i]=flist[i-1]*i%p

for i in range(q):
  x,d,n=(int(i) for i in input().split())
  if d==0:
    ans=pow(x,n,p)
  else:
    x=x*pow(d,p-2,p)%p    
    if p<=x+n-1:
      ans=0
    else:
      ans=pow(d,n,p)*flist[x+n-1]*pow(flist[x-1],p-2,p)%p
  print(ans%p)
N = input()
NB = list(N)
NN = int(N)

SN = 0
for i in N:
    SN += int(i)

if NB%SN == 0:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

S = list(input())

ans =0
for i in S:
    if i == "+" : ans += 1
    else: ans -= 1

print(ans)
def check(T, p, n, k):
    i = 0
    
    for j in range(k):
        s = 0
       
       while(s+T[i] <= p):
            s += T[i]
            i += 1
            if i == n:
                return n
    
    return i

n, k = [int(x) for x in input().split()]
T = []
for i in range(n):
    T.append(int(input()))

left, right = 0, 100000 * 10000

while(right - left > 1):
    mid = (left + right) / 2
    if (check(T, mid, n, k) >= n):
        right = mid
    else:
        left = mid

print right

### FIXED CODE ###

def check(T, p, n, k):
    i = 0
    
    for j in range(k):
        s = 0
       
        while(s+T[i] <= p):
            s += T[i]
            i += 1
            if i == n:
                return n
    
    return i

n, k = [int(x) for x in input().split()]
T = []
for i in range(n):
    T.append(int(input()))

left, right = 0, 100000 * 10000

while(right - left > 1):
    mid = int((left + right) / 2)
    if (check(T, mid, n, k) >= n):
        right = mid
    else:
        left = mid

print(right)
A, B, K = map(int, input().split())
max = max([A, B])
divideCount = 0

for i in range(1, max):
  if A % i == 0 && B % i == 0:
    if divideCount == K:
      print(i)
      return
    else:
      divideCount += 1


### FIXED CODE ###

A, B, K = map(int, input().split())
divideCount = 0
answer = 0

for i in range(100, 0, -1):
  if A % i == 0 and B % i == 0:
    divideCount += 1
    if divideCount == K:
      answer = i

print(answer)