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.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Locale;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader bf =  new BufferedReader(new InputStreamReader(System.in));
		//BufferedReader bf =  new BufferedReader(new FileReader("p.txt"));
		
		StringTokenizer tk = new StringTokenizer(bf.readLine());
		
		int casos = Integer.parseInt(tk.nextToken());
		
		for (int i = 0; i < casos; i++) {
			//System.out.println("*****"+i);
			tk = new StringTokenizer(bf.readLine());
			long n = Long.parseLong(tk.nextToken());
			long m = Long.parseLong(tk.nextToken());
			if(!(m>n)) {
				long M = cycleSum(m)*(n/(cycle(m)*m));
				long ps = m*cycle(m)*(n/(cycle(m)*m));

				for (int j = 1; j <= (n-ps)/m; j++) {
					M += (j*m)%10;
				}
				
				System.out.println(M);
			}else {
				System.out.println(0);
			}
		}			
	}
	
	static int cycle(long n) {
		
		if(n%10==0) return 1;
		if(n%2==0) 	return 5;
		if(n%5==0)  return 2;
		return 10;
		
	}
	
	static long cycleSum(long n) {
		
		long sum = 0;
		
		for (int i = 1; i <= cycle(n); i++) {
			sum += (n*i)%10;
		}
		
		return sum;
	}

}
