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