12043 - Divisors

定義兩個函數 d(n) 與 q(n)：

d(n) = 可整除 n 的整數個數。

q(n) = 可整除 n 的整數之總和。

在此我們定義可整除 n 的整數包含 1 與 n 本身，例如當 n = 6，可整除6的整數為1, 2, 3, 6，故 d(6) = 4; q(6) = 12。

另外，我們定義兩個函數 g(a, b, k) 與 h(a, b, k) 為

其中 a <= i <= b 且 i 可被 k 整除(羅馬符號sigma(i)即為q(i)，因譯者打不出該符號，故以q(n)代替)。

例如 g(5, 12, 3) = d(6) + d(9) + d(12) = 4 + 3 + 6 = 13 且 h(5, 12, 3) = q(6) + q(9) + q(12) = 12 + 13 + 28 = 53。本題給定 a, b, k 請你計算 g(a, b, k), h(a, b, k)。

Input

輸入的第一列有一個整數T(T <= 75)表示測試資料的組數，每組資料有三個整數a, b, k，且 0 < a <= b <= 100000; 0 < k < 2000。

Output

請針對每組測試資料，輸出 g(a, b, k) 與 h(a, b, k)，並以一個空白字元隔開。

Sample Input

2 
5 12 3 
1 100 3
        

Sample Output

13 53 
217 3323 

原文出處