Pretty good numbers

Time limit1sMemory limit128 MB

Summary

Count the integers in each interval whose absolute gap between the proper-divisor sum and the number is within the limit.

Level: Medium5 of 10
Topics: Number theory, Sorting, Prefix sum
Solved: No attempts yet

Problem

A perfect number is a natural number whose proper divisors add up to the number itself. The proper divisors of 6 are 1, 2 and 3, and 1+2+3 = 6, so 6 is perfect. 28 is perfect too, since 1+2+4+7+14 = 28.

The badness of a natural number is the difference between the sum of its proper divisors and the number itself, taken in absolute value. The badness of 10 is $|(1+2+5) - 10| = 2$ , and the badness of 20 is $|(1+2+4+5+10) - 20| = 2$ .

A pretty good number is a number whose badness stays within a given limit. If badness up to 2 is allowed, the pretty good numbers below 100 are 2, 3, 4, 6, 8, 10, 16, 20, 28, 32 and 64, so there are 11 of them. Setting the limit to 0 gives the definition of a perfect number.

Given the largest allowed badness and an interval, write a program that counts the pretty good numbers in that interval.

Input

The input consists of several test cases. Each test case is one line holding three integers start, stop and badness, separated by spaces.

$2 \le \text{start} < 1000000$
$\text{start} \le \text{stop} < 1000000$
$0 \le \text{badness} < 1000$

The last line holds three zeros. Do not process that line.

Output

For each test case print one line in the form Test i: c. Here i is the test case number counted from 1, and c is how many natural numbers n with $\text{start} \le n \le \text{stop}$ have badness at most badness. Both start and stop belong to the interval.

Examples1

Example 1

Input

2 100 2
2 100 0
1000 9999 3
0 0 0

Expected output

Test 1: 11
Test 2: 2
Test 3: 6