Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Book Reading

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPolycarp 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 \le q \le 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 \le n, m \le 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

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/02/2022 07:21:42 (g2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|