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.awt.*;
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;

import static java.lang.Math.*;

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer("");
    PrintWriter pw = new PrintWriter(System.out);

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

    String next() throws IOException {
        if (!st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

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

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

    public Main() throws FileNotFoundException {
    }

    public static void main(String[] args) throws IOException {
        new Main().run();
    }

    int b[][];

    long funk(TreeSet<Integer> left[], TreeSet<Integer>[] right, int[][] a, int[][] x, int k, int type) {
        long leftsum = 0;
        long rightsum = 0;
        while (true) {
            boolean yes = true;
            for (int i = 0; i < x.length; i++) {
                if (x[i][0] == 1) {
                    int p = left[i].first();
                    leftsum += a[p][2];
                    x[i][0] = 0;
                    left[i].remove(p);
                    right[a[p][1]].remove(i);
                    yes = false;
                }
            }
            if (yes) break;
            for (int i = 0; i < x.length; i++) {
                if (x[i][1] == 1) {
                    int p = right[i].first();
                    rightsum += a[p][2];
                    x[i][1] = 0;
                    right[i].remove(p);
                    left[a[p][0]].remove(i);
                }
            }
        }
        if (type == 0) {
            for (int i = 0; i < x.length; i++) {
                for (int j = 0; j < 2; j++) {
                    b[i][j] = x[i][j];
                }
            }
        }
        return leftsum * 100000000000000l + rightsum * 10000000;
    }

    void run() throws IOException {
        int q = nextInt();
        for (int i = 0; i < q; i++) {
            long n = nextLong();
            long m = nextLong();
            long count = n / m;
            long e = m % 10;
            long sum = 0;
            long x = e;
            long sumforlap = e;
            long lap = 1;
            while (true) {
                x += e;
                x %= 10;
                if (x == e) break;
                sumforlap += x;
                lap++;
            }
            sum += sumforlap * (count / lap);
            x = e;
            for (long l = 0; l < count % lap; l++) {
                sum += x;
                x += e;
                x %= 10;
            }
            pw.println(sum);
        }
        pw.close();
    }

    class Pair {
        int x, y;

        public Pair(int a, int b) {
            x = a;
            y = b;
        }
    }

    class PairComp implements Comparator<Pair> {

        @Override
        public int compare(Pair o1, Pair o2) {
            if (o1.x == o2.x) return Integer.compare(o1.y, o2.y);
            return Integer.compare(o1.x, o2.x);
        }
    }
}