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 sys import stdin,stdout,setrecursionlimit
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353
# from sys import stdin
# input = stdin.readline
#def data(): return sys.stdin.readline().strip()
def data(): return input()
def num():return int(input())
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]
def pmat(A):
    for ele in A:
        print(*ele,end="\n")
def seive():
    prime=[1 for i in range(10**6+1)]
    prime[0]=0
    prime[1]=0
    for i in range(10**6+1):
        if(prime[i]):
            for j in range(2*i,10**6+1,i):
                prime[j]=0
    return prime
#solution
for _ in range(int(data())):
    n,m=sp();ans=0;x=n//m;rem=x%10;mult=x//10;arr=[0]*10
    for i in range(1,11):arr[i-1]=(m*i)%10
    print(mult*(sum(arr))+sum(arr[:rem]))



'''
for _ in range(int(data())):
    n=int(data());a=L();ht={i:a[i] for i in range(n)};ans=[];t=False;ind=-1
    for i in range(1,n):
        if a[0]!=a[i]:
            ind=i
            ans.append((1,i+1))

    if ans:
        print('YES')
        for i in range(1,n):
            if a[0]==a[i]:
                ans.append((ind+1,i+1))
        pmat(ans)
    else:print('NO')

    
#
for _ in range(num()):
    n,k=map(int,input().split())
    arr=list(map(int,input().split()))
    csum=arr[0]
    for i in range(1,n):
        if((arr[i]*100)>(csum*k)):
            csum=ceil((arr[i]*100)/k)
        csum+=arr[i]
    print(csum-sum(arr))'''

endtime = time.time()
#print(f"Runtime of the program is {endtime - starttime}")

