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
'use strict'
 
const minus = (a, b, zero) => {
    if (a === b) return zero;
    const lA = a.length;
    const lB = b.length;
    if (lB < 15) return `${a.slice(0, -15)}${parseInt(a.slice(-15)) - parseInt(b)}`;
    const a15 = parseInt(a.slice(0, 15));
    const b15 = parseInt(b.slice(0, 15));
    return `${a15 - b15}${`000000000000000${parseInt(a.slice(15)) - parseInt(b.slice(15))}`.slice(lA - 15)}`;
};
 
const plus = (a, b) => {
    const lA = a.length;
    const lB = b.length;
    if (lB < 15 && lA < 15) return `${parseInt(a) + parseInt(b)}`;
 
    const a15 = parseInt(a.slice(-15));
    const b15 = parseInt(b.slice(-15));
 
    const s15 = `${a15 + b15}`;
    const big = parseInt(a.slice(0, -15) || 0) + parseInt(b.slice(0, -15) || 0) + parseInt(s15.slice(0, -15) || 0);
    return big ? `${big}${`000000000000000${parseInt(s15)}`.slice(-15)}` : s15;
};
 
const gt = (a, b, ifEqual) => {
    if (a === b) return !!ifEqual;
    const lA = a.length;
    const lB = b.length;
    if (lA > lB) return true;
    if (lA < lB) return false;
    if (lA < 15) return parseInt(a) > parseInt(b);
    const a15 = parseInt(a.slice(0, 15));
    const b15 = parseInt(b.slice(0, 15));
    if (a15 > b15) return true;
    if (a15 < b15) return false;
    return parseInt(a.slice(15)) > parseInt(b.slice(15));
};
 
const del = (a, b) => {
    if(!gt(a, b, true)) return '0';
	const lA = a.length
    const lB = b.length;
    const r = Array(lA - lB + 1 - +!gt(a.slice(0, lB), b, true)).fill(0);
    while (gt(a, b, true)) {
        const l = lB + +!gt(a.slice(0, lB), b, true);
        let i = 0, aB = a.slice(0, l);
        while (gt(aB, b, true)) { aB = minus(aB, b, ''); i++; }
        if (i) r[a.length - l] = i;
        a = `${aB}${a.slice(l)}`.replace(/^0+/, '')
    }
    return r.reverse().join('');
};
 
const times = (a, b) => {
    let r = '0';
    for (let i = 0; i < a; i++) r = plus(r, b);
    return r;
};
 
const _fn = (x) => {
    if (x[0] === x[1]) return x[1][x[1].length - 1];
    if (x[0].length === x[1].length && x[0] < x[1]) return 0;
    const m = parseInt(x[1][x[1].length - 1]);
    const k = del(x[0], x[1]);
    let r = '0';
 
    for (let i = 1; i < 10; i++) {
        r = plus(r, times(i * m % 10, del(plus(k, `${10 - i}`), '10')));
    }
    return r;
};
 
const fn = (x) => {
    if (gt(x[0], `${Number.MAX_SAFE_INTEGER}`) && x[1].length < 3) return _fn(x);
    if (x[0] === x[1]) return x[1][x[1].length - 1];
    if (x[0].length === x[1].length && x[0] < x[1]) return 0;
    const m = parseInt(x[1][x[1].length - 1]);
    const k = Math.floor(x[0].slice(0, -3) / x[1] * 1000 + x[0].slice(-3) / x[1]);
    let r = 0;
 
    for (let i = 1; i < 10; i++) {
        r += i * m % 10 * (Math.floor((k - i)/10) + 1);
    }
    if (r > Number.MAX_SAFE_INTEGER / 100) {
        let R = 0;
        for (let i = 1; i < 10; i++) {
            R += i * m % 10 * (Math.floor((parseInt(`${k}`.slice(3)) - i)/10) + 1);
        }
        return `${r}`.slice(0, -4) + `${R}`.slice(-4); 
    }
    return r;
}
 
for (let i = parseInt(readline()); i; i--)
    write(fn(readline().split(' ')) + '\n');