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
import math

def len_2_loop(divisor, arr):
    num_on = divisor % 2
    full_reps = (divisor - num_on) / 2
    total = full_reps * sum(arr) + sum(arr[:num_on])
    return total

def len_5_loop(divisor, arr):
    num_on = divisor % 5
    full_reps = (divisor - num_on) / 5
    total = full_reps * sum(arr) + sum(arr[:num_on])
    return total

def len_10_loop(divisor, arr):
    num_on = divisor % 10
    full_reps = (divisor - num_on) / 10
    total = full_reps * sum(arr) + sum(arr[:num_on])
    return total


q = int(raw_input()) # q queries

for i in range(q):
    n, m = map(int,raw_input().split()) # total pages and divisor
 
    '''total = 0
    start = m
    while start <= n:
        total += start % 10
        start += m
    print total'''

    five = [5,0]
    
    two = [2, 4, 6, 8, 0]
    four = [4, 8, 2, 6, 0]
    six = [6, 2, 8, 4, 0]
    eight = [8, 6, 4, 2, 0]

    one = [1,2,3,4,5,6,7,8,9,0]
    three = [3,6,9,2,5,8,1,4,7,0]
    seven = [7,4,1,8,5,2,9,6,3,0]
    nine = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

    
    
    last_digit = m % 10
    divisor = int(math.floor(n/m))
    if last_digit == 0:
        print 0
    elif last_digit == 1:
        print len_10_loop(divisor, one)
    elif last_digit == 5:
        print len_2_loop(divisor, five)
    elif last_digit == 2:
        print len_5_loop(divisor, two)
    elif last_digit == 4:
        print len_5_loop(divisor, four)
    elif last_digit == 6:
        print len_5_loop(divisor, six)
    elif last_digit == 8:
        print len_5_loop(divisor, eight)
    elif last_digit == 3:
        print len_10_loop(divisor, three)
    elif last_digit == 7:
        print len_10_loop(divisor, seven)
    elif last_digit == 9:
        print len_10_loop(divisor, nine)