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.