C. Book Reading

problem

Polycarp is reading a book consisting of nn pages numbered from 11 to nn. Every time he finishes the page with the number divisible by mm, he writes down the last digit of this page number. For example, if n=15n=15 and m=5m=5, pages divisible by mm are 5,10,155,10,15. Their last digits are 5,0,55,0,5 correspondingly, their sum is 1010.

Your task is to calculate the sum of all digits Polycarp has written down.

You have to answer qq independent queries.

Input

The first line of the input contains one integer qq (1≤q≤10001≤q≤1000) — the number of queries.

The following qq lines contain queries, one per line. Each query is given as two integers nn and mm (1≤n,m≤10161≤n,m≤1016) — 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

解题思路：

题意（个人理解）：

现在有n个人在排队，我们把在排在第一的编号记为1，第二的编号记为2，依次类推，第n个的编号记为n。
现在，店家小明在弄一个沙皮统计，他写了一个数字m，然后把1到n中能够整除m的数字的末尾数记录下来。
并且把所有能够整除的末位数加起来。

例如：
n=15 m=5
那么在1到15这些编号中，能整除5的数有 5 10 15 三个数。
他们的末位数（即个位数）分别为： 5 0 5
相加得到：10
则10便为小明所求得值。

思路：

首先，能被m整除的数的数量是n/m，手算一下(或者打表)可以发现能被m整除的数的个位会循环，循环节长度只和m的个位有关，循环节具体情况见代码。

例如：n=100 m=3

1-n能被3整除的有：3 6 9 12 15 18 21 24 27 30 33 36 ……99

余数分别为： 3 6 9 2 5 8 1 4 7 0 3 6 …… 9

发现循环节的个数有：10个数且和为3 + 6+9+2+5+8+1+4+7+0 = 45

所以最后的结果为：（n/m/循环节的个数） * 一个循环的和 + 不够一个循环节的和

C++代码实现：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;

ll n,m;

int temp[10][12] = {   //temp[i][0]  指m的个位i的循环节的长度
    {1,0},
    {10,1,2,3,4,5,6,7,8,9,0},
    {5,2,4,6,8,0},
    {10,3,6,9,2,5,8,1,4,7,0},
    {5,4,8,2,6,0},
    {2,5,0},
    {5,6,2,8,4,0},
    {10,7,4,1,8,5,2,9,6,3,0},
    {5,8,6,4,2,0},
    {10,9,8,7,6,5,4,3,2,1,0}
};

int main()
{
    int q;
    cin >> q;
    //每个数累加上前面的数
    for(int i = 0; i < 10; i++)
    {
        for(int j = 2; j <= temp[i][0]; j++)
        {
            temp[i][j] += temp[i][j-1];
        }
    }
    while(q--) {
        cin >> n >> m;
        ll num = n/m;
        m = m % 10;


        ll sum = temp[m][temp[m][0]];  //一个循环节

        sum = sum * (num / temp[m][0]);  //所有循环节的和
        
        num = num % temp[m][0];   //看是否有不满一个循环的情况，若有，累加不满的和
        if(num)
            sum += temp[m][num];

        cout << sum << endl;
    }
    return 0;
}

每日一言：

生活是忙忙碌碌，重要的是开开心心