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


def gao(a, b, c, n):
    if a == 0:
        return (n + 1) * (b // c)
    if a >= c or b >= c:
        tmp = gao(a % c, b % c, c, n)
        res = tmp + (a // c) * n * (n + 1) // 2 + (b // c) * (n + 1)
        return res
    m = (a * n + b) // c
    tmp = gao(c, c - b - 1, a, m - 1)
    res = (n * m - tmp)
    return res


def sum_2(n):
    return n * (n + 1) // 2

def main():
    T = int(input())
    for i in range(0, T):
        n, m = map(int, input().split())
        res = m * sum_2(n // m);
        res -= 10 * gao(m, 0, 10, n // m)
        print(res)
main()