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.math.*;
import java.util.*;

public class Main {
    static BigInteger N, M;
    static int[] sum_last_digits;
    static int cycle_size = 0;
    static void gen_sum_last_digits(){
        cycle_size = 0;
        boolean[] used = new boolean[10];
        sum_last_digits = new int[10];
        for(int i = 0; i < 10; i++){
            sum_last_digits[i] = 0;
        }
        String M_s = M.toString();
        int last_digit_M = Integer.parseInt(M_s.substring(M_s.length() - 1, M_s.length()));
        int last_digit_M_orig = last_digit_M;
        for(int s = 0; !used[last_digit_M]; s++){
            if(s != 0){
                sum_last_digits[s] += sum_last_digits[s - 1] + last_digit_M;
            }
            else{
                sum_last_digits[s] = last_digit_M;
            }
            used[last_digit_M] = true;
            last_digit_M = (last_digit_M + last_digit_M_orig) % 10;
            cycle_size++;
        }
    }

    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer in2 = new StringTokenizer(in.readLine());
        int Q = Integer.parseInt(in2.nextToken());
        for(int q = 0; q < Q; q++){
            in2 = new StringTokenizer(in.readLine());
            N = new BigInteger(in2.nextToken());
            M = new BigInteger(in2.nextToken());
            gen_sum_last_digits();

            BigInteger num_div_by_M = N.divide(M);
            BigInteger num_full_cycles = num_div_by_M.divide(new BigInteger(Integer.toString(cycle_size)));
            BigInteger rem = num_div_by_M.subtract(num_full_cycles.multiply(new BigInteger(Integer.toString(cycle_size))));
            BigInteger answer = num_full_cycles.multiply(new BigInteger(Integer.toString(sum_last_digits[cycle_size - 1])));
            BigInteger rem_cycle = new BigInteger("0");
            if(Integer.parseInt(rem.toString()) - 1 >= 0) {
                rem_cycle = new BigInteger(Integer.toString(sum_last_digits[Integer.parseInt(rem.toString()) - 1]));
            }
            answer = answer.add(rem_cycle);
            System.out.println(answer.toString());
        }
    }
}