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(input().strip())
for _ in range(q):
    addUp = 0
    store = []
    n, m = map(int, input().strip().split())
    #print(n, m)
#    for i in range(m, n + 1, m):
##        end = i % 10
##        addUp = addUp + end
##    print(addUp)
##        end = str(i)[-1]
##        addUp = addUp + int(end)
#        end = str(i)[-1]
#        store.append(int(end))
#    print(store)
#    print(sum(store))
    if m % 10 == 0:
        result = 0
    if m % 10 == 1:
        a1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
        b1 = [11, 22, 33, 44, 55, 66, 77, 88, 99, 110]
        d1 = [21, 42, 63, 84, 105, 126, 147, 168, 189, 210]
        e1 = [26, 52, 78, 104, 130]
        bb = 10 + 100 * (m // 10)
        #print(sum(a1) * (n // bb))
        aa = (n // bb) * bb
#        print(n, aa)
#        print(int(((n - aa) / bb) * 10))
#        print(a1[:int(((n - aa) / bb) * 10)])
#        print(sum(a1[:int(((n - aa) / bb) * 10)]))
        result = sum([1, 2, 3, 4, 5, 6, 7, 8, 9]) * (n // bb) + sum(a1[:int(((n - aa) / bb) * 10)])
    if m % 10 == 2:
        a1 = [2, 4, 6, 8, 0]
        b1 = [12, 24, 36, 48, 60]
        d1 = [22, 44, 66, 88, 100]
        e1 = [32, 64, 96, 128, 160]
        c1 = 10 + ((m // 10) * 50)
#        print(c1)
#        print(20 * (n // c1))
#        print(n, c1)
#        print(n % c1)
#        print(   int(((n % c1) / c1 * 10) / 2)       )
#        print(a1[:int(((n % c1) / c1 * 10) / 2)])
#        print(sum(a1[:((n % c1) * 10 ) // c1]))
        result = 20 * (n // c1) + sum(a1[:int(((n % c1) / c1 * 10) / 2)])
    if m % 10 == 3:
        a1 = [3, 6, 9, 2, 5, 8, 1, 4, 7, 0]
        cc = 30 + 100 * (m // 10)
        dd = (n // cc) * cc
        #print(a1[:int(((n - dd) / cc) * 10)])
        result = sum(a1) * (n // cc) + sum(a1[:int(((n - dd) / cc) * 10)])
    if m % 10 == 4:
        c1 = 20 + ((m // 10) * 50)
        a1 = [4, 8, 2, 6, 0]
#        print(c1)
#        print(20 * (n // c1))
#        print(n, c1)
#        print(n % c1)
#        print(   int(((n % c1) / c1 * 10) / 2)       )
#        print(a1[:int(((n % c1) / c1 * 10) / 2)])
#        print(sum(a1[:((n % c1) * 10 ) // c1]))
        result = 20 * (n // c1) + sum(a1[:int(((n % c1) / c1 * 10) / 2)])
        #print(result)
    if m % 10 == 5:
        if 0 <= n % (m * 2) <= (m // 10) * 10 + 4:
            a = n - n % (m * 2)
            #print(a)
            resu = int((a / m) / 2)
            #print(resu)
        else:
            a = n + ( m - n % (m * 2))
            #print(a)
            resu = int(((a - m) / m) / 2) + 1
            #print(resu)
        result = resu * 5
    if m % 10 == 6:
        c1 = 30 + ((m // 10) * 50)
        a1 = [6, 2, 8, 4, 0]
        b1 = [6, 12, 18, 24, 30]
        d1 = [16, 32, 48, 64, 80]
        e1 = [26, 52, 78, 104, 130]
#        print(c1)
#        print(20 * (n // c1))
#        print(n, c1)
#        print(n % c1)
#        print(   int(((n % c1) / c1 * 10) / 2)       )
#        print(a1[:int(((n % c1) / c1 * 10) / 2)])
#        print(sum(a1[:((n % c1) * 10 ) // c1]))
        result = 20 * (n // c1) + sum(a1[:int(((n % c1) / c1 * 10) / 2)])
        #print(result)
    if m % 10 == 7:
        a1 = [7, 4, 1, 8, 5, 2, 9, 6, 3, 0]
        b1 = [7, 14, 21, 28, 35, 42, 49, 56, 63, 70]
        d1 = [17, 34, 51, 68, 85, 102, 119, 136, 153, 170]
        e1 = [27, 54, 81, 108, 135, 162, 189, 216, 243, 270]
        cc = 70 + 100 * (m // 10)
        dd = (n // cc) * cc
        #print(a1[:int(((n - dd) / cc) * 10)])
        result = sum(a1) * (n // cc) + sum(a1[:int(((n - dd) / cc) * 10)])
    if m % 10 == 8:
        c1 = 40 + ((m // 10) * 50)
        a1 = [8, 6, 4, 2, 0]
        b1 = [8, 16, 24, 32, 40]
        d1 = [18, 36, 54, 72, 90]
        e1 = [28, 56, 84, 112, 140]
#        print(c1)
#        print(20 * (n // c1))
#        print(n, c1)
#        print(n % c1)
#        print(   int(((n % c1) / c1 * 10) / 2)       )
#        print(a1[:int(((n % c1) / c1 * 10) / 2)])
#        print(sum(a1[:((n % c1) * 10 ) // c1]))
        result = 20 * (n // c1) + sum(a1[:int(((n % c1) / c1 * 10) / 2)])
        #print(result)
    if m % 10 == 9:
        a1 = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
        b1 = [9, 18, 27, 36, 45, 54, 63, 72, 81, 90]
        d1 = [19, 38, 57, 76, 95, 114, 133, 152, 171, 190]
        e1 = [29, 58, 87, 116, 145, 174, 203, 232, 261, 290]
        #print(sum(a1))
        bb = 90 + 100 * (m // 10)
        #print(sum(a1) * (n // bb))
        aa = (n // bb) * bb
#        print(n, aa)
#        print(int(((n - aa) / bb) * 10))
#        print(a1[:int(((n - aa) / bb) * 10)])
#        print(sum(a1[:int(((n - aa) / bb) * 10)]))
        result = sum([1, 2, 3, 4, 5, 6, 7, 8, 9]) * (n // bb) + sum(a1[:int(((n - aa) / bb) * 10)])
    
    print(result)
    #print()