Ailin is a girl who likes numbers. This time she learned to calculate the sum of the divisors of a number. Her father, realizing she learns very fast, decides to ask her a more interesting version of that problem: Calculates the sum of the divisors of N which are not multiples of K. Input The first line contains a integer T, the number of cases (1 ≤ T ≤ 105). Each of the following lines T contains two integers N and K (1 ≤ N, K ≤ 5∗105). Output The output will contain T lines, each with the expected answer with the sum of divisors. Sample Input 5 20 2 10 1 20 5 75 20 40 Sample Output 6 0 7 8 42