DIVEQL - The Magical Bag

Dukkar has the magical bag of power 'P'. Here power 'P' of magical bag means any thing kept in the bag will be 'P' times.

Now Dukkar wanted to distribute equal number of Chocolates among his 'N' students using that magical bag in the following manner:-

Initially Dukkar has 'Z' chocolates and he give 'X' chocolates to first student and keep the remaining chocolates to magical bag so that it became 'P' times on next step, again he will take out 'X' chocolates from bag and give it to the second student and the remaining chocolates in the bag at this step will get 'P' time on the next step, this process continue.

Here you have to find minimum 'Z' so that at last step there are no chocolates in the magical bag (After giving 'X' chocolates to last student no chocolates should remain in bag)

Input

First line of input contain T (<100000) number of test cases and the following T lines will contain N (2<=N<=1018) and P (2<=P<=109).

Output

For each test case you have to print minimum 'Z' and corresponding 'X'. As answer can be large print answers modulo 1000000007.

(Z % 1000000007 and X % 1000000007)

Example

Input:
1
3 2

Output:
7 4

Explanation:

At Z=7, Initially Dukkar will give 4 chocolates to first student and keep 3 chocolates in bag. In the next step it became 6 now he gives 4 chocolates to second student. In the next step remaining 2 chocolates will be came 4 which he will give to third student. Now the bag became empty.


Added by:NISHANT RAJ
Date:2014-07-01
Time limit:5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own

hide comments
2014-07-02 17:25:47 adhikari vushesh babu
can you please tell me where my code fails ID:11872333

edit(Nishant):- you are not doing correctly

Last edit: 2014-07-02 16:12:35
2014-07-02 17:25:47 Samar Holkar
Please give some tricky test cases....

EDIT(Nishant) :-If you get the question then there is no tricky case..

@Nishant My code is getting WA repeatedly....please help me find out where it is inconsistant ........ http://***

EDIT(Nishant):- you should not post you code link here .. you doing wrong on line 29.

@Nishant Thanx...sir got AC....


Last edit: 2015-01-11 16:05:38
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.