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(raw_input())
for _ in xrange(t):
    n,m = map(int, raw_input().split())
    times = n // m
    extra = n % m
    lastdigit = m % 10
    zero = [0]
    one = [1,2,3,4,5,6,7,8,9,0]
    two = [2,4,6,8,0]
    three = [3,6,9,2,5,8,1,4,7,0]
    four = [4,8,2,6,0]
    five = [5,0]
    six = [6,2,8,4,0]
    seven = [7,4,1,8,5,2,9,6,3,0]
    eight = [8,6,4,2,0]
    nine = [9,8,7,6,5,4,3,2,1,0]
    
    ans = 0
    val = 0
    idx = 0
    if lastdigit == 0:
        times1 = times / len(zero)
        extra = times - (times1 * len(zero))
        for i in zero:
            val += i
        for i in xrange(extra):
            ans += zero[idx]
            idx += 1
    elif lastdigit == 1:
        times1 = times / len(one)
        extra = times - (times1 * len(one))
        for i in one:
            val += i
        for i in xrange(extra):
            ans += one[idx]
            idx += 1
    elif lastdigit == 2:
        times1 = times / len(two)
        extra = times - (times1 * len(two))
        for i in two:
            val += i
        for i in xrange(extra):
            ans += two[idx]
            idx += 1
    elif lastdigit == 3:
        times1 = times / len(three)
        extra = times - (times1 * len(three))
        #print times, times1, extra
        for i in three:
            val += i
        for i in xrange(extra):
            ans += three[idx]
            idx += 1
    elif lastdigit == 4:
        times1 = times / len(four)
        extra = times - (times1 * len(four))
        for i in four:
            val += i
        for i in xrange(extra):
            ans += four[idx]
            idx += 1
    elif lastdigit == 5:
        times1 = times / len(five)
        extra = times - (times1 * len(five))
        for i in five:
            val += i
        for i in xrange(extra):
            ans += five[idx]
            idx += 1
    elif lastdigit == 6:
        times1 = times / len(six)
        extra = times - (times1 * len(six))
        for i in six:
            val += i
        for i in xrange(extra):
            ans += six[idx]
            idx += 1
    elif lastdigit == 7:
        times1 = times / len(seven)
        extra = times - (times1 * len(seven))
        for i in seven:
            val += i
        for i in xrange(extra):
            ans += seven[idx]
            idx += 1
    elif lastdigit == 8:
        times1 = times / len(eight)
        extra = times - (times1 * len(eight))
        for i in eight:
            val += i
        for i in xrange(extra):
            ans += eight[idx]
            idx += 1
    elif lastdigit == 9:
        times1 = times / len(nine)
        extra = times - (times1 * len(nine))
        for i in nine:
            val += i
        for i in xrange(extra):
            ans += nine[idx]
            idx += 1
    ans += (times1 * val)
    
    print ans

