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.math.*;
import java.util.*;
public class practice{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int test_case = input.nextInt();
        BigInteger[] series = new BigInteger[test_case];
        for(int d = 0;d<test_case;d++){
        BigInteger n = input.nextBigInteger();
        BigInteger m = input.nextBigInteger();
        BigInteger i = new BigInteger("0");
        BigInteger o = new BigInteger("0");
        BigInteger j = new BigInteger("0");
        BigInteger k = new BigInteger("1");
        BigInteger p = new BigInteger("0");
        BigInteger sum = new BigInteger("0");
        BigInteger a = new BigInteger("10");
        BigInteger x = new BigInteger("10");
        BigInteger sub = new BigInteger("0");
        BigInteger y = new BigInteger("0");
        // a = m.multiply();

        i = n.divide(m);
        p = i.divide(a);
        j = i.mod(a);
        j = j.add(k);
        while(sub.compareTo(m.multiply(a)) <= 0){

             sum = sum.add(sub.mod(x));
             sub = m.add(sub);
             if(sub.compareTo(m.multiply(j)) == 0){
                y = sum;
             }
        
        }

        
        sum = sum.multiply(p);
        sum = sum.add(y);
        series[d]= sum;
    }
    for(int d = 0;d<test_case;d++){
        System.out.println(series[d]);
    }
        // System.out.println(p);
    }
}