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
T=int(input())
for _ in range(0,T):
    n,m=map(int,input().split())
    flag=0
    L=[]
    L.append(m%10)
    p=m
    while(flag==0):
        p=p+m
        if(p%10==L[0]):
            flag=1
            break
        else:
            L.append(p%10)

    #print(L)
    N=n//m
    sumu=0
    for i in range(0,len(L)):
        sumu+=L[i]

    q=N//len(L)
    r=N%len(L)

    ans=q*sumu

    for i in range(r):
        ans+=L[i]

    print(ans)
        
    
