- All Contests
- ProjectEuler+
- Project Euler #132: Large repunit factors

# Project Euler #132: Large repunit factors

# Project Euler #132: Large repunit factors

_{This problem is a programming version of Problem 132 from projecteuler.net}

A number consisting entirely of ones is called a repunit. We shall define to be a repunit of length .

For example, , and the sum of these prime factors is .

Given , and , find the sum of the first distinct prime factors of .

**Input Format**

The first line of input contains , the number of test cases.

Each test case consists of one line containing three space-separated integers, , and .

**Constraints**

is a multiple of

In test cases worth 1/3 of the total points:

In test cases worth 2/3 of the total points:

In test cases worth 3/3 of the total points:

**Output Format**

For each test case, output a single line containing a single integer, the answer for that test case.

**Sample Input**

```
1
10 9 2
```

**Sample Output**

```
28
```