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.