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 java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;
import java.io.IOException;
import java.util.ArrayList;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.Scanner;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.BitSet;
import java.io.IOException;
import java.util.Arrays;
import java.util.GregorianCalendar;
import java.util.List;


public class Main {

    static BigInteger modulo = new BigInteger("1000000007");
    static long mod = 1000000007;
//    int a;
//    Nested ststic class FastReaders
 
        
    static class FastReader {

        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException io) {
                    io.printStackTrace();
                }
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public String nextLine() {
            String s = "";
            try {
                s = br.readLine();
            } catch (IOException io) {
                io.printStackTrace();
            }
            return s;
        }
    }

    static BigInteger exponentialModulo(BigInteger a, BigInteger b) {
        BigInteger previousNumber = BigInteger.ONE;
        while (!(b.equals(BigInteger.valueOf(0)))) {
            if (b.testBit(0)) {
                previousNumber = previousNumber.multiply(a).mod(modulo);
            }
            b = b.shiftRight(1);
            a = a.modPow(BigInteger.valueOf(2), modulo);
        }
        return previousNumber;
    }

    public static int applySearchOfSubstring(String text) {
        int count = 0;
        Pattern p = Pattern.compile("AB");
        Matcher m = p.matcher(text);
        while (m.find()) {
            ++count;
        }
        return count;
    }

    public static void main(String[] args) throws IOException {
       FastReader input = new FastReader();
       
       int t = input.nextInt();
       while(t-- > 0){
           long n = input.nextLong();
           long m = input.nextLong();
           long ans = 0;
           for(long i = 0;i <= 10L;++i){
               ans += (n+(10-i)*m)/(m*10)*(m*i%10);
           }
           System.out.println(ans);
       }
    }
}
