- All Contests
- ProjectEuler+
- Project Euler #127: abc-hits

# Project Euler #127: abc-hits

# Project Euler #127: abc-hits

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

The radical of , , is the product of distinct prime factors of . For example, , so .

For a real number , we shall define the triplet of positive integers to be a *-abc-hit* if:

We will also call a *-abc-hit* simply an *abc-hit*.

For example, is an abc-hit, because:

It turns out that abc-hits are quite rare and there are only thirty-one abc-hits for , with .

Given and , what is for all -abc-hits where ?

**Input Format**

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

Each test case consists of a line containing two values, the real number and the integer , separated by a space.

**Constraints**

(Only the last test file has and is worth half the total points. For all the other test files, )

(The input is written with at most decimal digits behind the decimal point.)

**Output Format**

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

**Sample Input**

```
2
1.0 1000
1.5 1000
```

**Sample Output**

```
12523
424136
```

**Explanation**

The first test case corresponds to the example given in the problem statement.