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.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Scanner;


public class BookReading {
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner input =new Scanner(System.in);
		int q = input.nextInt();
		while(q-->0){
			long n = input.nextLong();
			long m = input.nextLong();
			//long i=1;
			long total=0;
			long val = m%10;
			long loop = (n/m);
			long[] d = new long[10];
		    long mandotary = loop/10;
			int rem = (int)(loop%10);
		    for(int i=1; i<10;i++){
				d[i] = mandotary;
				if(i<=rem)d[i]+=1;
			     total+=((int)((i*val)%10)*d[i]);
			}
			System.out.println(total);
		}
	}
	
/*
	static class Scanner {
		Scanner(InputStream in) { this.in = in; } InputStream in;
		int k, l; byte[] bb = new byte[1 << 15];
		byte getc() {
			if (k >= l) {
				k = 0;
				try { l = in.read(bb); } catch (IOException e) { l = 0; }
				if (l <= 0) return -1;
			}
			return bb[k++];
		}
		int nextInt() {
			byte c = 0; while (c <= 32) c = getc();
			int a = 0;
			while (c > 32) { a = a * 10 + c - '0'; c = getc(); }
			return a;
		}
		int m = 1 << 7; byte[] cc = new byte[m];
		int read() {
			byte c = 0; while (c <= 32) c = getc();
			int n = 0;
			while (c > 32) {
				if (n == m) cc = Arrays.copyOf(cc, m <<= 1);
				cc[n++] = c; c = getc();
			}
			return n;
		}
		byte[] nextBytes() { int n = read(); return Arrays.copyOf(cc, n); }
	}

*/
}
