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.*;
import java.math.*;
import java.util.*;
import javax.print.attribute.SetOfIntegerSyntax;
 
public class Solution{
    private static InputStream stream;
    private static byte[] buf = new byte[1024];
    private static int curChar;
    private static int numChars;
    private static SpaceCharFilter filter;
    private static PrintWriter pw;
    private static long count = 0,mod=100000,max=0;
    private static TreeSet<Integer>ts[]=new TreeSet[200000];
    private static ArrayList<Integer>[] adj;
    private static boolean visited[];
    
    public static void main(String args[]) throws Exception {
        InputReader(System.in);
        pw = new PrintWriter(System.out); 
        new Thread(null ,new Runnable(){
           public void run(){
               try{
                   soln();
                   pw.close();
               } catch(Exception e){
                   e.printStackTrace();
               }
           }
       },"1",1<<26).start();
    }
    //----------------------------------------My Code------------------------------------------------//
    private static ArrayList<Integer> prime;

    private static void sieve(int n) {
	    	boolean visited[] = new boolean[n];
	    	visited[1] =true;
	    	for(int i=2;i<n;i++) {
	    		if(!visited[i]) {
	    			prime.add(i);
	    			for(int j = i+i;j<n;j+=i) {
	    				visited[j] = true;
	    			}
	    		}
	    	}
    }
    private static void soln(){
    		int q = nextInt();
    		HashMap<Integer, ArrayList<Integer>> last_digits = new HashMap<>();
    		for( int i = 1; i<10 ;i++) {
    			ArrayList<Integer> last_digits_i = new ArrayList<Integer>();
    			for( int j = 1;j<10;j++) {
    				last_digits_i.add((i*j)%10);
    			}
    			last_digits.put(i, last_digits_i);
    		}
    		while (q-- > 0) {
    			 long n = nextLong(), m = nextLong();
    			 int m_unit = (int)(m%10);
    			 long full_mul = n / (m*10);
    			 long ans = 0;
    			 if (m>n || m_unit == 0) {
    				 System.out.println(ans);
    				 continue;
    			 }
    			 for( int x : last_digits.get(m_unit)) {
    				 ans += full_mul*x;
    			 }
    			 long part_mul = n % (m*10);
    			 part_mul /= m;
    			 for (int i = 0;i<part_mul;i++) {
    				 ans += last_digits.get(m_unit).get(i);
    			 }
    			 System.out.println(ans);
    		}
    }
    public static int bfs(int root, int key) {
    	boolean visited[] = new boolean[adj.length];
    	Queue<Integer> qu = new LinkedList<Integer>();
    	qu.add(root);
    	visited[root] = true;
    	int level = 0, increamenter = 1;//adj[root].size();
    	while(!qu.isEmpty()) {
    		int current = qu.poll();
    		if(current==key) return level;
    		increamenter--;
    		for(int x : adj[current]) {
    			if(!visited[x]) {
    				qu.add(x);
    				visited[x] = true;
    				if(x==key) return level+1;
    			}
    		}
    		if(increamenter==0) {
    			level++;
    			increamenter = qu.size();
    		}
    		//if(visited[key]) return level;
    	}
    	return 0;
    }
	//----------------------------------------THE END----------------------------------------------------------//            
	 
    static class Pair implements Comparable<Pair>{
 
       int idx,val;
       
        Pair(int idx,int val){
            this.idx=idx;
            this.val = val;
        }
        @Override
        public int compareTo(Pair o) {
           return Integer.compare(this.val, o.val);
            
        }
        //@Override
        public boolean equals(Pair o) {
        	return (this.idx==o.idx && this.val==o.val);
        }
        
        public int hashCode() {
        	return (Integer.hashCode(idx) + Integer.hashCode(val))%Integer.MAX_VALUE;
        }
    }
 
    public static long gcd(long x, long y) {
        if (x % y == 0)
            return y;
        else
            return gcd(y, x % y);
    }
    
    private static int BinarySearch(int a[], int low, int high, int target) {
        if (low > high)
            return -1;
        int mid = low + (high - low) / 2;
        if (a[mid] == target)
            return mid;
        if (a[mid] > target)
            high = mid - 1;
        if (a[mid] < target)
            low = mid + 1;
        return BinarySearch(a, low, high, target);
    }
    
    public static String reverseString(String s) {
        StringBuilder sb = new StringBuilder(s);
        sb.reverse();
        return (sb.toString());
    }
 
    
    
    public static long pow(long n, long p, long m) {
        long result = 1;
        if (p == 0)
            return 1;
        if (p == 1)
            return n;
        while (p != 0) {
            if (p % 2 == 1)
                result *= n;
            if (result >= m)
                result %= m;
            p >>= 1;
            n *= n;
            if (n >= m)
                n %= m;
        }
        return result;
    }
 
    public static long pow(long n, long p) {
        long result = 1;
        if (p == 0)
            return 1;
        if (p == 1)
            return n;
        while (p != 0) {
            if (p % 2 == 1)
                result *= n;
            p >>= 1;
            n *= n;
        }
        return result;
 
    }
 
     public static int[] radixSort(int[] f) {
        int[] to = new int[f.length];
        {
            int[] b = new int[65537];
            for (int i = 0; i < f.length; i++)
                b[1 + (f[i] & 0xffff)]++;
            for (int i = 1; i <= 65536; i++)
                b[i] += b[i - 1];
            for (int i = 0; i < f.length; i++)
                to[b[f[i] & 0xffff]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        {
            int[] b = new int[65537];
            for (int i = 0; i < f.length; i++)
                b[1 + (f[i] >>> 16)]++;
            for (int i = 1; i <= 65536; i++)
                b[i] += b[i - 1];
            for (int i = 0; i < f.length; i++)
                to[b[f[i] >>> 16]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        return f;
    }
 
    public static int nextPowerOf2(final int a) {
        int b = 1;
        while (b < a) {
            b = b << 1;
        }
        return b;
    }
 
    public static boolean PointInTriangle(int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8) {
        int s = p2 * p5 - p1 * p6 + (p6 - p2) * p7 + (p1 - p5) * p8;
        int t = p1 * p4 - p2 * p3 + (p2 - p4) * p7 + (p3 - p1) * p8;
 
        if ((s < 0) != (t < 0))
            return false;
 
        int A = -p4 * p5 + p2 * (p5 - p3) + p1 * (p4 - p6) + p3 * p6;
        if (A < 0.0) {
            s = -s;
            t = -t;
            A = -A;
        }
        return s > 0 && t > 0 && (s + t) <= A;
    }
 
    public static float area(int x1, int y1, int x2, int y2, int x3, int y3) {
        return (float) Math.abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0);
    }
 
    public static boolean isPrime(int n) {
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // This is checked so that we can skip 
    // middle five numbers in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
 
        return true;
    }
 
    //merge Sort
 
    static long sort(int a[])
    {  int n=a.length;
        int b[]=new int[n];    
        return mergeSort(a,b,0,n-1);}
    static long mergeSort(int a[],int b[],long left,long right)
    { long c=0;if(left<right)
     {   long mid=left+(right-left)/2;
         c= mergeSort(a,b,left,mid);
         c+=mergeSort(a,b,mid+1,right);
         c+=merge(a,b,left,mid+1,right); }    
        return c;     }
    static long merge(int a[],int  b[],long left,long mid,long right)
    {long c=0;int i=(int)left;int j=(int)mid; int k=(int)left;
    while(i<=(int)mid-1&&j<=(int)right)
    { if(a[i]>a[j]) {b[k++]=a[i++]; }
    else    { b[k++]=a[j++];c+=mid-i;}}
    while (i <= (int)mid - 1)   b[k++] = a[i++]; 
    while (j <= (int)right) b[k++] = a[j++];
    for (i=(int)left; i <= (int)right; i++) 
        a[i] = b[i];  return c;  }
 
    // To Get Input
// Some Buffer Methods
 
    public static void InputReader(InputStream stream1) {
        stream = stream1;
    }
 
    private static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
 
    private static boolean isEndOfLine(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }
 
    private static int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }
 
    private static int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
        sgn = -1;
        c = read();
    }
    int res = 0;
    do {
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
 
    private static long nextLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
        sgn = -1;
        c = read();
    }
    long res = 0;
    do {
        if (c < '0' || c > '9')
            throw new InputMismatchException();
        res *= 10;
        res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }
 
    private static String nextToken() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
 
    private static String nextLine() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isEndOfLine(c));
        return res.toString();
    }
 
    private static int[] nextIntArray(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }
        return arr;
    }
 
    private static int[][] next2dArray(int n, int m) {
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = nextInt();
            }
        }
        return arr;
    }
 
    private static long[] nextLongArray(int n) {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextLong();
        }
        return arr;
    }
 
    private static void pArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            pw.print(arr[i] + " ");
        }
        pw.println();
        return;
    }
 
    private static void pArray(long[] arr) {
        for (int i = 0; i < arr.length; i++) {
            pw.print(arr[i] + " ");
        }
        pw.println();
        return;
    }
 
    private static void pArray(boolean[] arr) {
        for (int i = 0; i < arr.length; i++) {
            pw.print(arr[i] + " ");
        }
        pw.println();
        return;
    }
 
    private static boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return isWhitespace(c);
    }
 
    private interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}