recursive-sums

Little Bear has received a home assignment to find the sum of all digits in a number N. Following his affinity towards single digit number, he intends to repeatedly compute the sum of all digits until the sum itself becomes a single digit number.

Can you write a program to compute the final single-digit sum?

As the number N is very big, it is given in the following run length encoded format - N is represented as a sequence of M blocks, where each block i (0 ≤ i < M) is represented by two integers - (len[i], d[i]). This implies that the digit d[i] occurs len[i] number of times.

For example, {(2,1), (1,2), (2,9)} represents the number 11299.

Input:
The first line contains a single integer T, denoting the number of test cases.
Each test case starts with a single integer M, which is the number of following run-length encoded blocks.
Each of the next M lines contains two space separated integers: len[i] and d[i].

Output:
Print the single-digit sum for each of the T test cases in a new line.

Constraints:
0 ≤ d[i] ≤ 9
1 ≤ len[i] ≤ 10^15
1 ≤ M ≤ 10^4
1 ≤ T ≤ 10

SAMPLE INPUT
3
3
2 1
1 2
2 9
1
8 1
3
2 5
1 4
1 5


SAMPLE OUTPUT
4
8
1

Explanation

Case 1:
The number is 11299.
We shall calculate the desired sum as: 1+1+2+9+9=2+2=4

Case 2:
The number is 11111111.
We shall calculate the desired sum as: 1+1+1+1+1+1+1+1=8

Case 3:
The number is 5545.
We shall calculate the desired sum as: 5+5+4+5=1+9=1+0=1

Difficulty: EASY
Tags: Implementation

Mathematics

Starter code:

Solutions:
t=int(input())
while t:
	res=0
	n=int(input())
	while n:
		a,b=list(map(int,input().split()))
		res=res+(a*b)
		n=n-1
	s=str(res)
	while len(s)>1:
		res=sum(map(int,list(s)))
		s=str(res)
	print(s)
	t=t-1


#=int(raw_input())
for t in range(int(input())):
	s=0
	for n in range(int(input())):
		a=[int(i) for i in input().split(" ")]
		s+=a[0]*a[1]
	s=str(s)
	
	while len(s)!=1:
		s1=0
		for i in s:
			s1+=int(i)
		s=str(s1)
	print(s)
			


def count_sum(length,integer,count):
	count += int(length)*int(integer)
	return count
def count_sum1(asum):
	count1 = 0
	for i in asum:
		count1 += int(i)
	return count1
	
	
T = eval(input())
res = ''
for i in range(T):
	M = eval(input())
	add = 0
	count = 0
	for j in range(M):
		length,integer = input().split()
		add += count_sum(length,integer,count)
	add = str(add)
	while len(add) != 1:
		add = count_sum1(add)
		add = str(add)
	res += add + '\n'
		
print(res)
	
		


def func(n):
	sum = 0
	while n:
		sum += n % 10
		n /= 10
	if sum > 9:
		return func(sum)
	return sum
		
t = int(input())
for i in range(t):
	n = int(input())
	sum = 0
	for j in range(n):
		s = input()
		x = int(s.split(" ")[0])
		y = int(s.split(" ")[1])
		sum += x * y
	print(func(sum))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'

def solve(x):
	if x<10:
		return x
	res = 0
	while x>0:
		res = res + x%10
		x = x/10
	
	return solve(res)


	
t = int(input())
while t>0:
	m = int(input())
	sm = 0
	while m>0:		
		line = input()		
		ln = int(line.split(' ')[0])
		d = int(line.split(' ')[1])
		sm += (ln*d)
		m -= 1
		
	print(solve(sm))
	t -= 1
	#cin >> t;
	#while(t--){
	#	int m;
	#	cin >> m;
	#	ull sum = 0;
	#	for(int i=0;i<m;++i){
	#		ull len,d;
	#		cin >> len >> d;
	#		sum += (len*d);
	##	cout << solve(sum) << endl;
	#}
	#



t = int(input())
def find_sum(s):
	if s < 10:
		return s
	else:
		su = 0
		while s>0:
			su += s%10
			s /=10
		return find_sum(su)
while t:
	s = 0
	t-=1
	m = int(input())
	for i in range(m):
		tup = list(map(int,input().split()))
		s += tup[0] * tup[1]
	print(find_sum(s))




def rec_sum(n):
	if n<10:
		return n
	else:
		return n%10+rec_sum(n/10)
		
t=int(input())
for _ in range(t):
	m=int(input())
	ans=0
	for i in range(m):
		l,d=list(map(int,input().split()))
		ans+=(d*l)
		ans=rec_sum(ans)
	print(rec_sum(ans))
		
	


t=int(input())
for ii in range(t):
	m=int(input())
	c=0
	for i in range(m):
		f,n=list(map(int,input().split(' ')))
		c+=f*n
	while c>9:
		z=list(str(c))
		c=0
		for x in z:
			c+=int(x)
	print(c)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t = eval(input())
for _ in range(t):
	n = eval(input())
	sum = 0
	for i in range(n):
		ip = input().split(' ')
		p = int(ip[0])
		q = int(ip[1])
		sum += p*q
	while sum >= 10:
		s = str(sum)
		sum = 0
		for c in s: sum += int(c)
	print(sum)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
#print 'Hello World!'
t=int(input())
while t>0:
	t-=1
	n=int(input())
	s=0
	while(n>0):
		n-=1
		a,b=input().split(" ")
		a,b=int(a),int(b)
		s+=a*b
	while(s/10>=1):
		n=s
		p=0
		while(n>0):
			r=n%10
			p+=r
			n=n//10
		s=p
	print(s)
		
	
		
		
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t = eval(input())
while t>0:
	m = eval(input())
	su = 0;
	for i in range(0,m):
		x = input()
		#print x
		x = x.split()
		#y = input()
		su = su + int(x[0])*int(x[1])
	while su>9:
		temp = su
		ans = 0
		while temp > 0:
			dig = temp%10
			ans = ans + dig
			temp = temp/10
		su = ans
	print(su)
	t = t-1;


def S(n):
	sum=0
	while(n):
		r = n%10 
		sum += r
		n //= 10
	return sum
store = []
for i in range (250):
    sum = i
    while(sum>=10):
	   sum = S(sum)
    store.append(sum)
t = int(input())
while(t):
    sum=0
    m = int(input())
    while(m):
	   a,b = list(map(int,input().split(" ")))
	   sum += a*b
	   m = m-1
    sum = S(sum)
    if(sum>250):
	   sum = S(sum)
    print((store[sum]))
    t = t-1


def calc(ans):
	if len(ans)==1:
		print(ans)
		return
	else:
		temp=0
		for i in range(len(ans)):
			temp+=int(ans[i])
		calc(str(temp))
t=int(input())
for k in range(t):
	m=int(input())
	ans=0
	for o in range(m):
		l,d=list(map(int,input().split()))
		ans+=(l*d)
	calc(str(ans))



def summ(a):
	if a<10:
		return a
	else:
		string_x = str(a)
		total = 0
		for char in string_x:
			total += int(char)
		if total<10:
			return total
		else:
			return summ(total)
T=int(input())
for t in range (0,T):
	n=int(input())
	a=0
	for i in range (0,n):
		b = [int(z) for z in input().split()]
		m=b[0]
		k=b[1]
		a=(m*k)+a
	c=summ(a)
	print(c)
		
	


T=int(input())
for j in range(0,T):
	M=int(input())
	ans = 0
	
	for i in range(0,M):
		A=list(map(int,input().split()))
		ans = ans + A[0]*A[1]

	    
	while (ans/10 > 0):
		t=0
		while (ans > 0):
			t = t + ans%10
			ans = ans/10
		ans	= t;
	
	print(ans)


import sys

def specOps(N):
	if N<10:
		return N
	else:
		return specOps(N%10+specOps(N/10))
	
L=list(map(int, sys.stdin.read().split()))
ctr=1

for x in range(L[0]):
	M=L[ctr]
	ctr+=1
	res=0
	for y in range(M):
		res+=(L[ctr]*L[ctr+1])
		ctr+=2
	print(specOps(res))	
		


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
T = int(input())
assert(T >= 1 and T <= 10)
for i in range(T):
	M = int(input())
	assert(M >= 1 and M <= pow(10,4))
	b = []
	for j in range(M):
		c = []
		c = [int(k) for k in input().split()]
		num = c[0]*c[1]
		b.append(num)
	for j in range(M):
		sm = str(b[j])
		while(len(sm) > 1):
			smlen = len(sm)
			smin = 0
			for k in range(smlen):
				smin += int(sm[k])
			sm = str(smin)
		b[j] = int(sm)
	sm = 0
	for j in range(M):
		sm += b[j]
	sm = str(sm)
	while(len(sm) > 1):
			smlen = len(sm)
			smin = 0
			for k in range(smlen):
				smin += int(sm[k])
			sm = str(smin)
	print(sm)
	
		


t = int(eval(input()))
for i in range(t):
	m = int(eval(input()))
	num = []
	for j in range(m):
		num.append(list(map(int, input().split())))
	sum1 = 0
	for i in range(m):
		sum1 += num[i][0]*num[i][1]
	while sum1 >= 10:
		sum2 = 0
		sum1 = list(map(int,list(str(sum1))))
		for i in range(len(sum1)):
			sum2 += sum1[i]
		sum1 = sum2
	print(sum1)
		


def su(a):
	b=str(a)
	c=0
	for i in b:
		c=c+int(i)
	if len(b)==1:
		return a
	
	
	else:
		return su(c)

for i in range(eval(input())):
	num=0
	for j in range(eval(input())):
		a,b=[int(p) for p in input().split()]
		num=num+b*a
	print(su(num))
		
	


test = int(input())
while(test):
	M = int(input())
	ans = 0
	for i in range(0,M):
		l,d = input().split()
		ans = ans + ( int(l)*int(d) )
	while((ans/10) > 0):
		num = str(ans)
		ans = 0
		for each in num:
			ans = ans + int(each)
	print(ans)
	test-=1


t=int(eval(input()))
while t > 0:
	m=int(eval(input()))
	res=0
	while m > 0:
		l=input()
		l,d=l.split()
		l=int(l)
		d=int(d)
		res=res+l*d
		m=m-1
	while res >= 10:
		num=res
		res=0
		while num > 0:
			res=res+num%10
			num=num/10
	print((str(res)))
	t=t-1


T=int(eval(input()))
i=0
while i<T:
	n=int(input())
	j=0
	a=[]
	b=[]
	while j<n:
		a=[int(x) for x in input().split() ]
		b+=[a[1]*a[0]]
		a=[]
		j=j+1

	
	while 1:
		k=sum(b)
		if k>=0 and k <=9:
			print(k)
			break
		
		else:
			b=[]
			c=list(str(k))
			b=list(map(int,c))
			c=[]
		
	   
		




	i=i+1



def sum_digit(n):
	if n < 10:
		return n
	else:
		ans = 0
		while n > 0:
			ans += n%10
			n /= 10

	return sum_digit(ans) 
	
t = eval(input())
while t > 0:
	m = eval(input())
	num = 0
	while m > 0:
		li, di = list(map(int, input().split()))
		num += (li*di)
		m -= 1
		
	print(sum_digit(num))
	t -= 1


import sys
T = int(sys.stdin.readline())
for case in range(T):
	M = int(sys.stdin.readline())
	num = 0
	for x in range(M): 
		[i,j] = [int(y) for y in sys.stdin.readline().split()]
		num += i*j
	while len(str(num)) > 1:
		num = sum([int(x) for x in str(num)])
	print(num)
		
		


t=eval(input());
for t in range (0,t):
	n=eval(input());
	sm=0;
	while(n>0):
		n=n-1;
		a,b=input().split(' ');
		a=int(a);
		b=int(b);
		sm=sm+(a*b);
	temp=sm;
	sm=0;
	while(temp>9):
		while(temp>0):
			sm=sm+temp%10;
			temp=temp/10;
		temp=sm;
		sm=0;

	print(temp);