Meepo's problem II

Time Limit: 8000/4000MS (Java/Others) Memory Limit: 384000/192000KB (Java/Others)

Problem Description

Meepo the Geomancer is a mischievous spirit of the earth who enjoys burying his enemies alive in mountains of rock spikes.

We all know that Meepo can summons some duplicate of himself, the clones are independent to each other and have the same abilities as Meepo.

When the Kth Meepo clone be summoned, this clone gain F(K,D) extra damage.

Here F(K,D) means the Kth small prime factor of D, where D is the primary Meepo's damage.

For example if primary Meepo's damage is 12, F(1,12) = 2.

And if K is bigger than the numbers of D's prim factor, F(K,D) = D.

Now if Meepo's damge range is [Li , Ri] , he want to know his Kth clone's damage range.


First line a number n (n ≤ 100000), means Meepo's query.

Next n line, 3 positive integer a line: Li, Ri, K, means Meepo's damage range is [Li, Ri], and he wants to know his Kth clone's damage range.

All Li, Ri, and K are no more than 500000 and Li ≤ Ri.


For every query, print two integer [L, R], means Meepo's clone's damage range.

Sample Input

17 47 3
11 36 7
3 16 1

Sample Output

34 94
22 72
6 26




Solved Number4
Submit Number4
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^