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
q = int(raw_input())

y = int('1234312817382646')

def sum_last_digit(n, m):
    if n < m:
        return 0

    if n == m:
        return n % 10

    cycle = set([])

    # if n == 1234312817382646:
        # print n,m,n/m

    i = 1
    while i < n/m+1:
        # print i*m%10
        if i*m%10 not in cycle:
            cycle.add(i*m%10)
            i += 1
        else:
            # print 'break'
            break

    # if n == 1234312817382646:
        # print cycle

    length = len(cycle)

    remaining = n/m % length
    output = sum(list(cycle)) * (n/m/length)

    for i in xrange(1, remaining+1):
        output += i*m%10

    return output

for abc in xrange(q):
    # n, m = [int(x) for x in raw_input().split()]
    inp = raw_input().split()
    n = int(inp[0])
    m = int(inp[1])
    # if n == 1234312817382646:
    #     print n, m
    print sum_last_digit(n, m)
