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
//package main;

import java.io.*;
import java.util.*;

public final class Main {
    BufferedReader br;
    StringTokenizer stk;
    
    public static void main(String[] args) throws Exception {
        new Main().run();
    }
    
    {
        stk = null;
        br = new BufferedReader(new InputStreamReader(System.in));
    }
    
    long mod = 998244353;
    StringBuilder res = new StringBuilder(1000005);
    void run() throws Exception {
        int t = ni();
        while(t-- > 0) {
            long n = nl(), k = nl();
            int[] arr = new int[10000];
            long value = k;
            for(int i = 0; i < 10000; i++) {
                arr[i] = (int)(value % 10);
                value = arr[i] + k;
            }
            int len = cycle(arr);
            
            int[] a = new int[len];
            for(int i = 0; i < len; i++) {
                a[i] = arr[i];
            }
            long sum = Arrays.stream(a).sum();
            
            long pages = n / k;
            long ans = sum * (pages / len);
            long rem = pages % len;
            for(int i = 0; i < rem; i++) {
                ans += a[i];
            }
            
            res.append(ans).append("\n");
        }
        System.out.print(res);
    }
    
    int cycle(int[] arr) {
        for(int i = 1; i < arr.length; i++) {
            boolean ok = true;
            for(int j = 0; j < arr.length; j++) {
                if(arr[j] != arr[j % i]) {
                    ok = false;
                    break;
                }
            }
            if(ok) {
                return i;
            }
        }
        return -1;
    }
    
    //Reader & Writer
    String nextToken() throws Exception {
        if (stk == null || !stk.hasMoreTokens())
            stk = new StringTokenizer(br.readLine(), " ");
        return stk.nextToken();
    }

    String nt() throws Exception {
        return nextToken();
    }

    int ni() throws Exception {
        return Integer.parseInt(nextToken());
    }

    long nl() throws Exception {
        return Long.parseLong(nextToken());
    }
    
    double nd() throws Exception {
        return Double.parseDouble(nextToken());
    }
    
    //Some Misc methods
    int get(int l, int r, int[] a) {
        return l == 0 ? a[r] : a[r] - a[l - 1];
    }
    
    void shuffle(int[] a) {
        Random r = new Random();
        for(int i = 0; i < a.length; i++) {
            int idx = r.nextInt(a.length);
            int temp = a[i];
            a[i] = a[idx];
            a[idx] = temp;
        }
    }
}