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