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

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.

3 17 47 3 11 36 7 3 16 1

34 94 22 72 6 26

eggeek