Elon Musk has succesfully built an automated staircase from Earth to Mars. Many people want to go to Mars, but that's not possible due to limited capacity of the staircase and logistics involved. Hence, Elon asks interested candidates to solve a tough challenge. If they solve it, they get a chance to visit Mars, otherwise not. Sam is highly interested in going to Mars. Can you help him solve the challenge? 

The staircase has N steps. One can either go step by step, or at each step, can take a jump of at most N steps. 

Elon is interested to know the number of ways in which you can go to Mars. Since the number of steps in stairs can be insanely large, Elon is only interested in the first and the last K digits of number of ways from which he can compute the actual answer with his algorithm.

Input Format

   First line is an integer T that denotes the number of test cases.

   Next T lines contain 2 integers each, N and K.

Output Format

  T lines. Each line corresponds to one of the test cases and contains the sum of numbers which are formed by first K digit and last K digits of number of ways.

Constraints

1<=T<=1000
1<=N<=10^9
1<=K<=9

If S is the number of ways in which one can climb the staircase, then 
the number of digits in S is greater or equal to the K.

Sample Input

2
10 2 
12 1

Sample Output

63
10

If there are 10 steps, let's call the number of ways in which one can go is 
S

let S be of the form wxyz. 

So, summing wx + yz gives 63.

Difficulty: MEDIUM
Tags: Combinatorics

Starter code:

Solutions:
from math import log10, ceil
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	n -= 1
	c = 2 * ceil(k + log10(n))
	e = n
	b = 2
	s = 1
	while e > 0:
		if e % 2 == 1:
			s = int(str(s * b)[:c])
		e //= 2
		b = int(str(b * b)[:c])
	s = str(s)[:k]
	r = int(s) + pow(2, n, 10 ** k)
	print(r)


def exp_mod(n, x, p):
	if n == 0:
		return 1
	t = exp_mod(n // 2, x, p)
	if n % 2 == 1:
		return t * t * x % p
	else:
		return t * t % p

def exp_mod_f(n, x, p):
	if n == 0:
		return 1
	t = exp_mod_f(n // 2, x, p)
	res = 1
	if n % 2 == 1:
		res = t * t * x
	else:
		res = t * t
	while res > p:
		res //= 10
	return res
t = int(input())
for i in range(t):
	n_l = input()
	a = [int(x) for x in n_l.split()]
	z0 = 10 ** a[1]
	z2 = 10 ** (a[1] + 140)
	l = exp_mod(a[0] - 1, 2, z0)
	f = exp_mod_f(a[0] - 1, 2, z2)
	while l > z0:
		l //= 10
	while f >= z0:
		f //= 10
	print(l + f)


import sys, math
from decimal import Decimal

def firstK(n, k):
	x = Decimal(n) * Decimal(2).log10()
	frac = x % 1
	return math.floor(10 ** frac * 10 ** (k - 1))

def lastK(n, k):
	m = 10 ** k
	if n < 10000:
		return 2 ** n % m
	x = 2 ** 10000 % m
	(d, r) = divmod(n, 10000)
	if n < 1000000:
		return x ** d % m * (2 ** r % m) % m
	x2 = x ** 100 % m
	(d2, r2) = divmod(d, 100)
	return x2 ** d2 % m * (x ** r2 % m) % m * (2 ** r % m) % m
number_of_cases = int(sys.stdin.readline())
for line in sys.stdin:
	(n, k) = [int(x) for x in line.split()]
	print(firstK(n - 1, k) + lastK(n - 1, k))


from decimal import *
getcontext().prec = 100
period = [0, 4, 20, 100, 500, 2500, 12500, 62500, 312500, 1562500]
last = []
large = 10000000000

def build_last():
	value = 1
	for i in range(1562510):
		last.append(value)
		value *= 2
		if value > large:
			value %= large

def last_K(n, k):
	per = period[k]
	index = n % per
	if index < k:
		index += per
	large_value = last[index]
	mod = 10 ** k
	return large_value % mod

def first_K(n, k):
	n = Decimal(n)
	k = Decimal(k)
	lg = n * Decimal(2).log10()
	lg -= lg.quantize(Decimal(1), rounding=ROUND_FLOOR) - k + Decimal(1)
	return (Decimal(10) ** lg).quantize(Decimal(1), rounding=ROUND_FLOOR)
build_last()
t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	n = n - 1
	a = last_K(n, k)
	b = first_K(n, k)
	print(a + b)


from decimal import *
import math
getcontext().prec = 50
T = int(input())
for i in range(T):
	curr = input().split()
	N = int(curr[0])
	K = int(curr[1])
	a = Decimal(N - 1) * Decimal(2).log10()
	st = str(a)
	b = st.find('.')
	frac = Decimal('0' + st[b:])
	first = int(10 ** (frac + K - 1))
	second = pow(2, N - 1, 10 ** K)
	res = first + second
	print(res)


import decimal, math, sys
decimal.getcontext().prec = 25
log2 = decimal.Decimal(2).log10()
num_digits = lambda n: 1 + int(n * log2)
sum_digits = lambda n: sum(map(int, str(n)))

def first_digits(n, m):
	if m > num_digits(n):
		m = num_digits(n)
	x = 10 ** (n * log2 - (num_digits(n) - m))
	return int(x)

def last_digits(n, m):
	if m > num_digits(n):
		m = num_digits(n)
	powers_map = {0: 1, 1: 2}
	mod = 10 ** m
	while max(powers_map) <= n // 2 + 1:
		k = max(powers_map)
		powers_map[2 * k] = powers_map[k] ** 2
		powers_map[2 * k] %= mod
	product = 1
	while n > 0:
		k = max(filter(lambda x: x <= n, powers_map))
		n -= k
		product *= powers_map[k]
		product %= mod
	return product
T = int(sys.stdin.readline())
for i in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	print(first_digits(N - 1, K) + last_digits(N - 1, K))


import sys, math
from decimal import *
T = int(input().strip())
if T > 1000 or T < 1:
	sys.exit(1)
for t in range(0, T):
	(N, K) = [int(i) for i in input().strip().split()]
	getcontext().prec = 80
	aux = Decimal(2).log10() * (N - 1)
	first = Decimal(10 ** (aux % 1 + K - 1))
	last = 1
	mod = 10 ** K
	base = 2
	exponent = N - 1
	while exponent > 0:
		if exponent % 2 == 1:
			last = last * base % mod
		exponent = exponent >> 1
		base = base * base % mod
	print(int(str(first)[:K]) + int(str(last)[-K:]))


import decimal, math, sys
decimal.getcontext().prec = 25
log2 = decimal.Decimal(2).log10()
num_digits = lambda n: 1 + int(n * log2)
sum_digits = lambda n: sum(map(int, str(n)))

def first_digits(n, m):
	if m > num_digits(n):
		m = num_digits(n)
	x = 10 ** (n * log2 - (num_digits(n) - m))
	return int(x)

def last_digits(n, m):
	if m > num_digits(n):
		m = num_digits(n)
	powers_map = {0: 1, 1: 2}
	mod = 10 ** m
	while max(powers_map) <= n // 2 + 1:
		k = max(powers_map)
		powers_map[2 * k] = powers_map[k] ** 2
		powers_map[2 * k] %= mod
	product = 1
	while n > 0:
		k = max(filter(lambda x: x <= n, powers_map))
		n -= k
		product *= powers_map[k]
		product %= mod
	return product
T = int(sys.stdin.readline())
for i in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	print(first_digits(N - 1, K) + last_digits(N - 1, K))


t = int(input())
h = 0
from decimal import Decimal
while t > h:
	w = input().split(' ')
	n = int(w[0])
	k = int(w[1])
	bol = False
	c = k
	p = '1' + k * '0'
	f = pow(2, n - 1, int(p))
	b = '1' + k * '0'
	magic = Decimal(2).log10()
	digits = magic * (n - 1) % 1
	ls = int(10 ** (k - 1 + digits))
	print(f + ls)
	h += 1


from math import log
from decimal import *
getcontext().prec = 50
log2_10 = Decimal('2').log10()
for case in range(int(input())):
	(n, k) = map(int, input().split())
	a = pow(2, n - 1, 10 ** k)
	b = int(Decimal('10') ** (Decimal(n - 1) * log2_10 % 1) * 10 ** (k - 1))
	print(a + b)


import decimal, math, sys
decimal.getcontext().prec = 25
log2 = decimal.Decimal(2).log10()
num_digits = lambda n: 1 + int(n * log2)
sum_digits = lambda n: sum(map(int, str(n)))

def first_digits(n, m):
	if m > num_digits(n):
		m = num_digits(n)
	x = 10 ** (n * log2 - (num_digits(n) - m))
	return int(x)

def last_digits(n, m):
	if m > num_digits(n):
		m = num_digits(n)
	powers_map = {0: 1, 1: 2}
	mod = 10 ** m
	while max(powers_map) <= n // 2 + 1:
		k = max(powers_map)
		powers_map[2 * k] = powers_map[k] ** 2
		powers_map[2 * k] %= mod
	product = 1
	while n > 0:
		k = max(filter(lambda x: x <= n, powers_map))
		n -= k
		product *= powers_map[k]
		product %= mod
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	print(first_digits(N - 1, K) + last_digits(N - 1, K))


import decimal, math, sys
decimal.getcontext().prec = 25
log2 = decimal.Decimal(2).log10()
num_digits = lambda n: 1 + int(n * log2)
sum_digits = lambda n: sum(map(int, str(n)))

def first_digits(n, m):
	if m > num_digits(n):
		m = num_digits(n)
	x = 10 ** (n * log2 - (num_digits(n) - m))
	return int(x)

def last_digits(n, m):
	if m > num_digits(n):
		m = num_digits(n)
	powers_map = {0: 1, 1: 2}
	mod = 10 ** m
	while max(powers_map) <= n // 2 + 1:
		k = max(powers_map)
		powers_map[2 * k] = powers_map[k] ** 2
		powers_map[2 * k] %= mod
	product = 1
	while n > 0:
		k = max(filter(lambda x: x <= n, powers_map))
		n -= k
		product *= powers_map[k]
		product %= mod
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	print(first_digits(N - 1, K) + last_digits(N - 1, K))


from functools import reduce

def truncate(num, digits):
	return int(str(num)[:digits])
power_table = [2] * 31
for i in range(1, 31):
	power_table[i] = truncate(power_table[i - 1] ** 2, 50)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	exponent = '{0:b}'.format(n - 1)
	n_powers = len(exponent)
	first_part = reduce(lambda x, y: truncate(x * y, 50), [power_table[i] for i in range(n_powers) if exponent[n_powers - i - 1] == '1'], 1)
	last_part = pow(2, n - 1, 10 ** k)
	print(truncate(first_part, k) + last_part)


from math import log10, ceil
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	n -= 1
	c = 2 * ceil(k + log10(n))
	e = n
	b = 2
	s = 1
	while e > 0:
		if e % 2 == 1:
			s = int(str(s * b)[:c])
		e //= 2
		b = int(str(b * b)[:c])
	s = str(s)[:k]
	r = int(s) + pow(2, n, 10 ** k)
	print(r)


from sys import stdin
from itertools import accumulate as acc, count, combinations_with_replacement as cmbrep, takewhile as tkw, repeat as rp, dropwhile as dpw, combinations as comb
from functools import reduce
from random import randint
from collections import Counter
from math import sqrt, log, factorial
from fractions import gcd
from heapq import merge
from array import array
filou = None
from os.path import basename, exists, expanduser, splitext, isfile
from os import getcwd
lolPath = getcwd()
randid = '\\qosdjfoiz.txt'
home = isfile(lolPath + randid)
if home:
	filou = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\JourneyIn03.txt'
	filin = 'D:\\ZeDaddy\\Documents\\Hack\\combinatorics\\JourneyOu03.txt'
else:
	filou = None
if home:
	from mesures import ch, prof
trace = 0
prof = 0
tst = 0

def exp4(po):
	return reduce(lambda r, b: r * r << b, map(int, bin(po)[2:]), 1)

def exp5(po, K):
	r = 1
	for b in map(int, bin(po)[2:]):
		r = r * r << b
		while r > 10 ** 30:
			r //= 10
	while r > 10 ** K:
		r //= 10
	return r

def HB(N, K):
	B = pow(2, N, 10 ** K)
	H = exp5(N, K + 3)
	while H >= 10 ** K:
		H //= 10
	return H + B
if home:
	reff = open(filin)
rd = open(filou) if filou else stdin
for _ in range(int(rd.readline().strip())):
	(N, K) = map(int, rd.readline().strip().split())
	clc = HB(N - 1, K)
	if home:
		ref = int(reff.readline().strip())
		if clc != ref:
			print(HB(N - 1, K), ref)
	else:
		print(clc)


import decimal, math, sys
decimal.getcontext().prec = 25
log2 = decimal.Decimal(2).log10()
num_digits = lambda n: 1 + int(n * log2)
sum_digits = lambda n: sum(map(int, str(n)))

def first_digits(n, m):
	if m > num_digits(n):
		m = num_digits(n)
	x = 10 ** (n * log2 - (num_digits(n) - m))
	return int(x)

def last_digits(n, m):
	if m > num_digits(n):
		m = num_digits(n)
	powers_map = {0: 1, 1: 2}
	mod = 10 ** m
	while max(powers_map) <= n // 2 + 1:
		k = max(powers_map)
		powers_map[2 * k] = powers_map[k] ** 2
		powers_map[2 * k] %= mod
	product = 1
	while n > 0:
		k = max(filter(lambda x: x <= n, powers_map))
		n -= k
		product *= powers_map[k]
		product %= mod
	return product
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	print(first_digits(N - 1, K) + last_digits(N - 1, K))


def getC3(B):
	C = []
	while B > 0:
		d = int(math.log(B, 2))
		k = 2 ** d
		B -= k
		C.append(k)
	return C

def solve2(A, B, K):
	C = getC3(B)
	i = 1
	D0 = {1: A}
	D1 = {1: A}
	A0 = A
	A1 = A
	L = 24
	k0 = 10 ** K
	while i < C[0]:
		A0 = A0 * A0 % k0
		A1 = A1 * A1
		if len(str(A1)) > K + L:
			A1 = int(str(A1)[:K + L])
		i *= 2
		if i in C:
			D0[i] = A0
			D1[i] = A1
	for i in range(1, len(C)):
		A0 = A0 * D0[C[i]] % k0
		A1 = A1 * D1[C[i]]
		if len(str(A1)) > K + L:
			A1 = int(str(A1)[:K + L])
	return A0 + int(str(A1)[:K])
import math
T = int(input())
for t0 in range(T):
	(N, K) = [int(a) for a in input().split()]
	print(solve2(2, N - 1, K))


def pwr(b, e, mod):
	b %= mod
	if e == 0:
		return 1
	if e == 1:
		return b
	return pwr(b * b, e // 2, mod) * pwr(b, e % 2, mod) % mod

def pwr2(b, e, keep=18):
	b = int(str(b)[0:keep])
	if e == 0:
		return 1
	if e == 1:
		return b
	b = pwr2(b * b, e // 2, keep) * pwr2(b, e % 2, keep)
	b = int(str(b)[0:keep])
	return b
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(2 if n == 1 else pwr(2, n - 1, 10 ** k) + int(str(pwr2(2, n - 1))[0:k]))


from decimal import *

def expmod(a, b, m):
	p = 1
	while b > 0:
		if b % 2 == 1:
			p = p * a % m
		b //= 2
		a = a * a % m
	return p
T = int(input())
for run in range(T):
	(n, k) = [int(i) for i in input().split()]
	r = (n - 1) * Decimal(2).log10()
	m = r - int(r) + k - 1
	p = int(10 ** m)
	q = expmod(2, n - 1, 10 ** k)
	print(int(p) + q)


from math import log, ceil
from decimal import *
getcontext().prec = 100

def mypow(a, p, d):
	res = 1
	while p:
		if p % 2:
			res *= a
			while res > d:
				res //= 10
		a *= a
		while a > d:
			a //= 10
		p //= 2
	return res
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if n < 10:
		x = str(2 ** n)
		last = int(x[-k:])
		first = int(x[:k])
	else:
		last = pow(2, n - 1, 10 ** k)
		x = k + 2 * int(ceil(log(n - 1, 10)))
		first = int(str(mypow(2, n - 1, 10 ** x))[:k])
	print(last + first)


from decimal import *

def bitize(x, power=2):
	L = []
	while x > 0:
		L.append(x % power)
		x //= power
	if not L:
		L = [0]
	return L

def pow_mod(a, b, mod=13):
	result = 1
	bits = bitize(b)
	a_power = a
	for bit in bits:
		if bit:
			result *= a_power
			result %= mod
		a_power *= a_power
		a_power %= mod
	return result

def pow_bin(a, b):
	result = Decimal(1)
	bits = bitize(b)
	a_power = Decimal(a)
	for bit in bits:
		if bit:
			result *= a_power
		a_power *= a_power
		while result < 0.1:
			result *= Decimal(10)
		while a_power < 0.01:
			a_power *= Decimal(100)
	return result

def compute_steps(N, K):
	lower_digits = pow_mod(2, N - 1, pow(10, K))
	upper_digits = int(Decimal(pow(10, K - 1)) / Decimal(pow_bin(0.5, N - 1)))
	return upper_digits + lower_digits
T = int(input())
for _ in range(T):
	(N, K) = [int(a) for a in input().split()]
	print(compute_steps(N, K))


import math
from decimal import *
getcontext().prec = 20
t = int(input())
for i in range(t):
	L = list(map(int, input().split()))
	x = pow(2, L[0] - 1, 10 ** L[1])
	z = (L[0] - 1) * Decimal(2).log10()
	y = str(int(pow(10, z - math.floor(z)) * 10 ** 20))
	print(x + int(y[:L[1]]))


from decimal import *
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	Flog = (N - 1) * Decimal(2).log10()
	Flog -= Flog.to_integral(rounding=ROUND_FLOOR)
	F = (Decimal(10) ** (Flog + K - 1)).to_integral(rounding=ROUND_FLOOR)
	L = pow(2, N - 1, 10 ** K)
	print(F + L)


import sys

def calc_bf(n):
	cache = [0] * (n + 1)
	cache[0] = 1
	for i in range(1, n + 1):
		sm = 0
		for j in range(i):
			sm += cache[j]
		cache[i] = sm
	print('\tcache=%s' % (cache,), file=sys.stderr)
	return cache[n]

def rdigit_gen(n):
	if n == 0:
		yield 0
	else:
		while n:
			yield (n % 10)
			n //= 10

def combine(rdd):
	(sm, f) = (0, 1)
	for d in rdd:
		sm += f * d
		f *= 10
	return sm

def solve(n, k):
	print('n=%d k=%d' % (n, k), file=sys.stderr)
	b = pow(2, n - 1, pow(10, k))
	print('\tb=%d' % (b,), file=sys.stderr)
	(f, a) = (2, 1)
	i = n - 1
	delta = max(k + 1, 20)
	while i:
		print('\ti=%d a=%d f=%d' % (i, a, f), file=sys.stderr)
		if i % 2 == 1:
			a *= f
			a = combine(list(rdigit_gen(a))[-delta:])
		v = combine(list(rdigit_gen(f))[-delta:])
		f = pow(v, 2)
		i //= 2
	print('\ta=%d' % (a,), file=sys.stderr)
	a = combine(list(rdigit_gen(a))[-k:])
	print('\ta=%d' % (a,), file=sys.stderr)
	return a + b
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k))


from decimal import Decimal
T = int(input())
for t in range(T):
	(N, K) = map(int, input().split())
	x = Decimal(2).log10() * (N - 1)
	hi = int(10 ** (x - (int(x) - K + 1)))
	lo = pow(2, N - 1, 10 ** K)
	print(hi + lo)


from decimal import *
import math
getcontext().prec = 50
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = Decimal(n - 1) * Decimal(2).log10()
	st = str(a)
	b = st.find('.')
	f = Decimal('0' + st[b:])
	n1 = int(10 ** (f + k - 1))
	n2 = pow(2, n - 1, 10 ** k)
	print(n1 + n2)


from math import log10, ceil
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	n -= 1
	temp = 2 * ceil(k + log10(n))
	(x, y, z) = (n, 2, 1)
	while x > 0:
		if x % 2 == 1:
			z = int(str(z * y)[:temp])
		x //= 2
		y = int(str(y * y)[:temp])
	z = str(z)[:k]
	print(int(z) + pow(2, n, 10 ** k))


from math import log10, ceil
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	n -= 1
	c = 2 * ceil(k + log10(n))
	e = n
	b = 2
	s = 1
	while e > 0:
		if e % 2 == 1:
			s = int(str(s * b)[:c])
		e //= 2
		b = int(str(b * b)[:c])
	s = str(s)[:k]
	r = int(s) + pow(2, n, 10 ** k)
	print(r)


from math import log10, ceil
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	n -= 1
	c = 2 * ceil(k + log10(n))
	e = n
	b = 2
	s = 1
	while e > 0:
		if e % 2 == 1:
			s = int(str(s * b)[:c])
		e //= 2
		b = int(str(b * b)[:c])
	s = str(s)[:k]
	r = int(s) + pow(2, n, 10 ** k)
	print(r)


from math import log10, ceil
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	n -= 1
	c = 2 * ceil(k + log10(n))
	e = n
	b = 2
	s = 1
	while e > 0:
		if e % 2 == 1:
			s = int(str(s * b)[:c])
		e //= 2
		b = int(str(b * b)[:c])
	s = str(s)[:k]
	r = int(s) + pow(2, n, 10 ** k)
	print(r)


from math import log10, ceil
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	n -= 1
	c = 2 * ceil(k + log10(n))
	e = n
	b = 2
	s = 1
	while e > 0:
		if e % 2 == 1:
			s = int(str(s * b)[:c])
		e //= 2
		b = int(str(b * b)[:c])
	s = str(s)[:k]
	r = int(s) + pow(2, n, 10 ** k)
	print(r)


from math import log10, ceil
T = int(input())
for _ in range(T):
	(n, k) = [int(x) for x in input().split()]
	n -= 1
	c = 2 * ceil(k + log10(n))
	e = n
	b = 2
	s = 1
	while e > 0:
		if e % 2 == 1:
			s = int(str(s * b)[:c])
		e //= 2
		b = int(str(b * b)[:c])
	s = str(s)[:k]
	r = int(s) + pow(2, n, 10 ** k)
	print(r)