Migrated from Lutece 773 Nisepanda Dai Kazoku

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Long long ago, There are only two kind of Nisepanda. Every year, some of them will changed to another type, for example type $A$ will become type $B$, and vice versa.

After a long-time research, we find the rule of their evolution: suppose that there are exactly $N$ Nisepandas numbered from $1$ to $N$, and after the $k_{th}$ year, the Nisepandas numbered $k,2\times k,3\times k\cdots m\times k$($m\times k\leq n$) will get changed to another type.

Now, Nispandas are very Curious about the number of type $A$ and type $B$ nidepanda after $M$ years(count from $1$).

Inintially, all the Nisepandas are type $A$ in $1_{th}$ year.

As Nisepandas are all uneducated, they can only remember some number that very close to $N$, that is to say for every $M$, $|M-N|\leq 1000$ will be satisfied.

Input

The input consists of several test cases. There is a single number on the first line $T$, the number of cases. Following $T$ lines contains two numbers $n$ and $m$($0\leq n\leq 10^{12}, 0\leq m$), representing the number of the Nisepandas and the number of years passed.

Output

For each case, print two numbers in a single line, representing the number of type $A$ and the number of type $B$.

Samples

2
5 0
5 4

5 0
2 3

Resources

第五届ACM趣味程序设计竞赛第四场（正式赛）