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.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
	public static void main(String args[]) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int c = Integer.parseInt(br.readLine());
		int [][]sum = new int[10][20];
		int []length = new int[10];
		for(int i=1; i<=9; ++i) {
			int init = i, count = 1;
			sum[i][count] = init;
			while(init != 0) {
				++count;
				init = (init + i) % 10;
				sum[i][count] = sum[i][count-1] + init;
			}
			length[i] = count;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<c; ++i) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			long n = Long.parseLong(st.nextToken());
			long m = Long.parseLong(st.nextToken());
			int lastDigit = (int) (m % 10);
			
			if(lastDigit == 0) {
				sb.append("0\n");
				continue;
			}
			
			long incl = n / m;
			long mul = incl / length[lastDigit];
			int remainder = (int) (incl % length[lastDigit]);
			BigInteger res = BigInteger.ZERO;
			BigInteger bMal = BigInteger.valueOf(mul);
			BigInteger bSum = BigInteger.valueOf(sum[lastDigit][length[lastDigit]]);
			BigInteger bReSum = BigInteger.valueOf(sum[lastDigit][remainder]);
			res = res.add(bMal.multiply(bSum)).add(bReSum);
			
			sb.append(res + "\n");
		}
		System.out.print(sb);
	}
}
