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
tc = int(input())
for _ in range(tc):
    n,m = list(map(int,input().split()))
    summ = 0

    total = n //m
    # print('s',total)
    lis = list()

    for i in range(m,n+1,m):
        last = str(i)[-1]
        last = int(last)
        if last not in lis:
            lis.append(last)
            total-=1
            summ += last
        else:
            ind = lis.index(last)
            lis = lis[ind:]
            break
    
    if len(lis)>0:
        # print(lis)
        ls = sum(lis)
        if total>=len(lis):
            no = total//len(lis)
            summ += ls*no
            total-= len(lis)*no
        if total>0:
            no = lis[:total]
            summ += sum(no)



    # for i in range(m,n,m):
    #     last = str(i)[-1]
    #     summ += int(last)

    # i = 1
    # mm =m
    # while mm<n:
    #     last = list(str(m))[-1]
    #     summ += int(last)
    #     i+=1
    #     mm = mm+m

    if m == n:
        print(str(m)[-1])
    else:
        print(summ)