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
n=int(input())
for j in range(n):
    s=0
    a,b=input().split()
    a=int(a)
    b=int(b)
    u=[]
    i=0
    while i>=0:
        if i%10 in u:
            k=i
            break
        if i%10 not in u:
            u.append(i%10)#last digits repeat itself so we find the interval at which it reapeats (k). the series occurs a//k times, eg for 100 and 3 the last digits repaet after 30 , last digits (3,6,9,2,1,7,4,8,5,7) sum  to give 45 , 100//30=3 therefore 45*33=135 is sum from 0 to 30*3(=90) hence we need to find sum from numbers 90 to 100 that is k*(a//k) to a 
        i+=b
    s=sum(u)
    ss=0
    for i in range((a//k)*k,a+1,b):
        ss+=i%10
    sss=s*(a//k)+ss
    print(sss)


