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.

Input

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.

Output

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

Sample Input

3
17 47 3
11 36 7
3 16 1

Sample Output

34 94
22 72
6 26

Source

eggeek

Manager

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