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.util.*;
import java.math.*;
public class cb {
	
    InputStream is;
    PrintWriter out; 
	
	static int mod=(int)1e9+7;
	

    void solve()
    {
		int a1[]={1,2,3,4,5,6,7,8,9,0};
		int a2[]={2,4,6,8,0};
		int a3[]={3,6,9,2,5,8,1,4,7,0};
		int a4[]={4,8,2,6,0};
		int a5[]={5,0};
		int a6[]={6,2,8,4,0};
		int a7[]={7,4,1,8,5,2,9,6,3,0};
		int a8[]={8,6,4,2,0};
		int a9[]={9,8,7,6,5,4,3,2,1,0};
		int t=ni();
		while(t-->0)
		{
			long nm1=nl();
			long nm2=nl();
			long mid=(nm1/nm2);
			long ans=0;
			if(nm2%10==1)
			{
				 ans=(mid/10)*(45L);
				for(int i=0;i<mid%10;i++)
					ans+=a1[i];
			}
			else if(nm2%10==2)
			{
				 ans=(mid/5)*(20L);
				for(int i=0;i<mid%5;i++)
					ans+=a2[i];
			}
			else if(nm2%10==3)
			{
				 ans=(mid/10)*(45L);
				for(int i=0;i<mid%10;i++)
					ans+=a3[i];
			}
			else if(nm2%10==4)
			{
				 ans=(mid/5)*(20L);
				for(int i=0;i<mid%5;i++)
					ans+=a4[i];
			}
			else if(nm2%10==5)
			{
				 ans=(mid/2)*(5L);
				for(int i=0;i<mid%2;i++)
					ans+=a5[i];
			}
			else if(nm2%10==6)
			{
				 ans=(mid/5)*(20L);
				for(int i=0;i<mid%5;i++)
					ans+=a6[i];
			}
			else if(nm2%10==7)
			{
				 ans=(mid/10)*(45L);
				for(int i=0;i<mid%10;i++)
					ans+=a7[i];
			}
			else if(nm2%10==8)
			{
				 ans=(mid/5)*(20L);
				for(int i=0;i<mid%5;i++)
					ans+=a8[i];
			}
			else if(nm2%10==9)
			{
				 ans=(mid/10)*(45L);
				for(int i=0;i<mid%10;i++)
					ans+=a9[i];
			}
			out.println(ans);
		}
	}
	
	
	
	
 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	 
	
	
 
 
 
	
	public static long [][] multiply(long a[][],long b[][])
	{
		long mul[][]=new long[2][2];
		for(int i=0;i<2;i++)
		{
			for(int j=0;j<2;j++)
			{
				mul[i][j]=0;
				for(int k=0;k<2;k++)
					mul[i][j]=(mul[i][j]+(a[i][k]*b[k][j]))%mod;
			}
		}
		return mul;
	}
	
	/* Matrix Exponention*/
	public static long [][] power(long [][] mat,int n)
	{
		long res[][]=new long[2][2];
		res[0][0]=1;res[1][1]=1;
		while(n>0)
		{
			if(n%2==1)
				res=multiply(res,mat);
			mat=multiply(mat,mat);
			n/=2;
		}
		return res;
	}
	  
	  
	  
	
    //---------- I/O Template ----------
    
    public static void main(String[] args) { new cb().run(); }
    void run() { 
        is = System.in; 
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }
    
    byte input[] = new byte[1024];
    int len = 0, ptr = 0;
    
    int readByte() { 
        if(ptr >= len) { ptr = 0; 
            try { len = is.read(input); } 
            catch(IOException e) { throw new InputMismatchException(); } 
            if(len <= 0) { return -1; } 
        } return input[ptr++];
    }
    boolean isSpaceChar(int c) { return !( c >= 33 && c <= 126 ); }
    int skip() { 
        int b = readByte(); 
        while(b != -1 && isSpaceChar(b)) { b = readByte(); } 
        return b;
    }
    
    char nc() { return (char)skip(); }
    String ns() { 
        int b = skip(); 
        StringBuilder sb = new StringBuilder(); 
        while(!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } 
        return sb.toString();
    }
    String nLine() { 
        int b = skip(); 
        StringBuilder sb = new StringBuilder(); 
        while( !(isSpaceChar(b) && b != ' ') ) { sb.appendCodePoint(b); b = readByte(); } 
        return sb.toString();
    }
    int ni() { 
        int n = 0, b = readByte(); 
        boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        if(b == -1) { return -1; }  //no input 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }
    long nl() { 
        long n = 0L;    int b = readByte(); 
        boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }
 
    double nd() { return Double.parseDouble(ns()); }
    float nf() { return Float.parseFloat(ns()); }
    int[] na(int n) { 
        int a[] = new int[n]; 
        for(int i = 0; i < n; i++) { a[i] = ni(); } 
        return a;
    }
    char[] ns(int n) { 
        char c[] = new char[n]; 
        int i, b = skip(); 
        for(i = 0; i < n; i++) { 
            if(isSpaceChar(b)) { break; } 
            c[i] = (char)b; b = readByte(); 
        } return i == n ? c : Arrays.copyOf(c,i);
    }
	
}