C. Book Reading

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Copy

7
1 1
10 1
100 3
1024 14
998244353 1337
123 144
1234312817382646 13

output

Copy

1
45
153
294
3359835
0
427262129093995

解题说明：此题是一道模拟题，找规律求解。首先，能被m整除的数的数量是n/m，可以发现能被m整除的数的个位会循环，循环节长度只和m的个位有关，最后的结果为：（n/m/循环节的个数） *   一个循环的和 +  不够一个循环节的和。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int main()
{
	long long n, m, t;
	scanf("%I64d", &t);
	while (t--)
	{
		scanf("%I64d%I64d", &n, &m);
		long long sum = 0, c, d, i;
		for (i = m; i <= m * 9; i += m)
		{
			sum += i % 10;
		}
		c = n / (m * 10);
		d = c * sum;
		c = c * (m * 10);
		for (i = c + m; i <= n; i += m)
		{
			d += i % 10;
		}
		printf("%I64d\n", d);
	}
	return 0;
}