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
k = int(input())
for ga in range(k):
  a = input().split()
  n = int(a[0])
  m = int(a[1])
  ga = 0
  summ = 0
  m1 = m * 2
  m1s = m 
  ms = m
  summs = 0
  while int(str(m)[-1]) != int(str(m1)[-1]):
    m1 += m
    summ += int(str(m1)[-1])
    ga += 1
  ga += 1
  m1 += m
  summ += int(str(m1)[-1])
  ggg = int((n// m) // ga)
  if n < m:
    print(0)
  else:
    if ggg >= 1:
      summs += ggg * summ
      if int((n// m)) % ga != 0:
        for i in range(int((n// m)) % ga):
          summs += int(str(m1s)[-1])
          m1s += ms
      else:
        pass
    else:
      for i in range(n // m ):
        summs += int(str(m1s)[-1])
        m1s += m
    print(summs)