As Bill moves further into the round panel asks him is there anything he is very good at. Bill tells them he is pretty good at questions related to divisors, factors and all. Based on this Panel gives him Q queries. In each Query they give him two integers N and K. He needs to give them the sum of first K factors of N(First K factors means when all the factors of N are arranged in increasing order you need to consider first K factors).

Constraints:
1 ≤ Q ≤ 10⁵
1 ≤ N ≤ 10⁵
1 ≤ K ≤ Number of Factors of N

Input:
First line contains the number of Queries Q.
Each Query contains two integers N and K.

Output:
For each query print the required sum in a new line.