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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.util.NoSuchElementException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Ruins He
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskC solver = new TaskC();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, InputReader in, OutputWriter out) {
            long n = in.nextLong();
            long m = in.nextLong();

            int[] position = new int[10];
            Arrays.fill(position, -1);
            int circle = 0;
            int offset = -1;
            for (int i = 1; m * i <= n; i++) {
                int d = (int) (m * i % 10);
                if (position[d] != -1) {
                    offset = position[d] - 1;
                    break;
                } else {
                    position[d] = i;
                    circle++;
                }
            }

            out.println(calculate(n, m, offset, circle));
        }

        private long calculate(long n, long m, int offset, int circle) {
            long total = (n - offset + m - 1) / m, one = 0, sum = 0;
            for (int i = 1; i <= offset; i++) {
                sum += m * i % 10;
            }
            for (int i = 1; i <= circle; i++) {
                one += m * (offset + i) % 10;
            }
            long start = 0;
            if (offset != -1) {
                sum += (total - offset) / circle * one;
                start = offset + (total - offset) / circle * m * circle;
            }
            for (int i = 1; ; i++) {
                long next = start + m * i;
                if (next > n) {
                    break;
                }
                sum += next % 10;
            }
            return sum;
        }

    }

    static class InputReader {
        public final BufferedReader reader;
        public StringTokenizer tokenizer = null;

        public InputReader(Reader reader) {
            this.reader = new BufferedReader(reader, 32767);
        }

        public InputReader(InputStream inputStream) {
            this(new InputStreamReader(inputStream));
        }

        public String next() {
            if (hasNext()) return tokenizer.nextToken();
            else throw new NoSuchElementException();
        }

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

        public boolean hasNext() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    String nextLine = reader.readLine();
                    if (nextLine == null) return false;
                    tokenizer = new StringTokenizer(nextLine);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.hasMoreTokens();
        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        private OutputWriter(Writer writer, boolean autoFlush) {
            this.writer = new PrintWriter(new BufferedWriter(writer, 32767), autoFlush);
        }

        public OutputWriter(Writer writer) {
            this(writer, true);
        }

        public OutputWriter(OutputStream outputStream) {
            this(new OutputStreamWriter(outputStream), false);
        }

        public OutputWriter println(long value) {
            writer.println(value);
            return this;
        }

        public void close() {
            writer.close();
        }

    }
}

