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.*;

public class Main {

	public static void main(String[] args) {
		InputReader in = new InputReader(System.in);
		int t = in.nextInt();
		while (t-- > 0) {
			long n = in.nextLong(), m = in.nextLong();
			if(m%10 == 0) {
				System.out.println(0);
			}else if(m%5 == 0){
				if((n/m)%2 == 1) {
					long ans = ((n/m)/2 + 1)*5;
					System.out.println(ans);
				}else {
					long ans = ((n/m)/2)*5;
					System.out.println(ans);
				}
			}else if((m&1) != 0) {
				long num = n/m;
				long ans = (num/10)*45;
				for(int i = 0; i < num%10; i++) {
					ans += (m*(i+1))%10;
				}
				System.out.println(ans);
			}else {
				long num = n/m;
				long ans = (num/10)*40;
				for(int i = 0; i < num%10; i++) {
					ans += (m*(i+1))%10;
				}
				System.out.println(ans);
			}
		}
	}

	static void sort_rev(int[] a) {
		Arrays.sort(a);
		int n = a.length;
		for (int i = 0; i < n / 2; i++) {
			swap(a, i, n - i - 1);
		}
	}

	static void swap(int[] a, int i, int j) {
		int t = a[i];
		a[i] = a[j];
		a[j] = t;
	}

	static void printArray(int[] a) {
		for (int val : a) {
			System.out.print(val + " ");
		}
		System.out.println();
	}
}

class InputReader {
	public BufferedReader reader;
	public StringTokenizer tokenizer;

	public InputReader(InputStream stream) {
		reader = new BufferedReader(new InputStreamReader(stream), 32768);
		tokenizer = null;
	}

	public String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	long nextLong() {
		return Long.parseLong(next());
	}

	double nextDouble() {
		return Double.parseDouble(next());
	}

	String nextLine() {
		String str = "";
		try {
			str = reader.readLine();
		} catch (IOException e) {
			e.printStackTrace();
		}
		return str;
	}

}