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 math
def god(n,k):
    s=0 
    if(k==0):
        return 0 
    if(k==1):
        return n%10 
    s+=n%10 
    if(k==2):
        return s+(2*n)%10
    s+=(2*n)%10 
    if(k==3):
        return s+(3*n)%10
    s+=(3*n)%10
    if(k==4):
        return s+(4*n)%10
    s+=(4*n)%10
    if(k==5):
        return s+(5*n)%10
    s+=(5*n)%10
    if(k==6):
        return s+(6*n)%10
    s+=(6*n)%10
    if(k==7):
        return s+(7*n)%10
    s+=(7*n)%10
    if(k==8):
        return s+(8*n)%10
    s+=(8*n)%10
    if(k==9):
        return s+(9*n)%10
    s+=(9*n)%10
for i in range(int(input())):
    n,m = map(int,input().split())
    c = n //m
    g=c//10 
    q= c%10 
    print(g*god(m,9)+god(m,q))
    
    