Polycarp is reading a book consisting of n pages numbered from 1 to n. Every time he finishes the page with the number divisible by m, he writes down the last digit of this page number. For example, if n=15 and m=5, pages divisible by m are 5, 10, 15. Their last digits are 5, 0, 5 correspondingly, their sum is 10.

Your task is to calculate the sum of all digits Polycarp has written down.

You have to answer q independent queries.

Input

The first line of the input contains one integer q (1 ≤ q ≤ 1000) — the number of queries.

The following q lines contain queries, one per line. Each query is given as two integers n and m (1 ≤ n, m ≤ 10^{16}) — the number of pages in the book and required divisor, respectively.

Output

For each query print the answer for it — the sum of digits written down by Polycarp.

Example

Input


7
1 1
10 1
100 3
1024 14
998244353 1337
123 144
1234312817382646 13


Output


1
45
153
294
3359835
0
427262129093995
from math import ceil, log, floor, sqrt
	
def mod_expo(n, p, m):
	"""find (n^p)%m"""
	result = 1
	while p != 0:
		if p%2 == 1:
			result = (result * n)%m
		p //= 2
		n = (n * n)%m
	return result
	
def find_product(n, m, arr):
	"""find |arr i - arr j| mod m"""
	product=1
	if n <= m:
		for i in range(n):
			for j in range(i+1, n):
				 product = (product * abs(arr[i] - arr[j]))%m
		return product
	return 0

def count_tables(l):
	count=0
	l.sort()
	a = l[1]-l[0]
	b = l[2]-l[0]
	if a%3 > 0 and (a%3 + (b - (a - a%3))) >= 3:
		count += 1
	count += l[0] + (2*a)//3
	return int(min(sum(l)/3, l[0] + l[1]))
	
def find_possible_weight(W, arr):
	w = 0
	for i in range(8, 0, -1):
		 count = min(arr[i-1], W//i)
		 w += count * i
		 W -= count * i
		 #print(count)
	return w
	
def find_divisor(a):
	divisors = []
	for i in range(2, min(a, ceil(sqrt(a))+1)):
		if a%i == 0:
			if a/i == i:
				divisors.append(i)
			else:
				divisors.append(i)
				divisors.append(a/i)
	if len(divisors) == 0:
		return -1
	return int(min(divisors))

def find_sum(n, m):
	prod = []
	total, res, index = 0, 0, 0
	for i in range(1, 10):
		prod.append((m*i)%10)
	total = sum(prod)
	res += (n//(10*m)) * total
	n -= (n//(10*m)) * (10*m)
	count = n//m
	while count:
		#print(i)
		res += prod[index]
		count -= 1
		index += 1
	return res
	
t = 1
t = int(input())
while t:
	t = t - 1
	#n = int(input()) 
	# a, b, m = map(int, input().split()) 
	n, m = map(int, input().split())
		#l = list(map(int, input().strip().split()))[:n]
	#str1 = input()
	#if no_vacancy(n, l):
	#	print("Yes")
	#else:
	#	print("No")
	print(find_sum(n, m))
