Description
대통령은 비밀 요원들을 관리하고 있다. 각 요원은 1번부터 N번까지의 고유 번호를 가지고 있고 대통령은 요원들에게 특별한 보너스를 지급하려고 하는데, 보너스 금액은 각 요원 번호의 약수의 개수에 비례한다.
예를 들어, 6번 요원의 약수는 1, 2, 3, 6으로 총 4개이므로 4만 원을 받게 된다. 하지만 대통령은 예산이 무한하지 않기 때문에 한 가지 제한을 두었는데 그것은 요원의 약수 개수가 대통령이 정한 제한 수치 M을 초과하는 경우, 그 요원은 너무 많은 보너스를 받지 못하도록 강제로 약수의 개수 대신 미리 지정된 고정 수치 K만큼만 보너스를 받게 된다.
1번 요원부터 N번 요원까지 국왕이 지급해야 하는 총 보너스의 합을 구하는 프로그램을 작성하시오.
Input
첫 번째 줄에 테스트케이스의 수 T가 정수로 주어지고 그 다음 줄부터 T줄만큼 세 개의 정수 N, M, K가 공백을 사이에 두고 주어진다. 단, 조건은 아래와 같다.
-
1 <= T <= 10
-
1 <= N <=100,000
-
1 <= M <= 100
-
1 <= K <= 10
Output
각 테스트케이스별로 요원들이 받는 총 보너스의 합을 한 줄에 하나씩 출력한다.