DIVEQL - The Magical Bag

no tags 

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 answer modulo 1000000007.

(Z%1000000007 and X % 1000000007)

Example


Input:
1
3 2
Output:
7 4
Explanation:-

As Z=7 ,Initially dukkar will give 4 chocolates to first student and kepp 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.


hide comments
Parul Yadav: 2015-09-05 17:18:28

easy one

Shashank Tiwari: 2015-07-12 11:14:12

Just consider Gcd and try to prove why it will be 1.

newbie: 2015-06-10 13:57:15

easy one...no tricky cases

Raghav Aggiwal Again: 2015-01-16 18:03:58

Forgetting a newline at the end of output caused me 7 wa.. :(

Abhishek: 2014-12-25 09:36:40

NZEC error , please check my submission

Vamsi Krishna Avula: 2014-12-25 06:51:48

Nishant Raj sir, can you please tell me why code is getting NZEC? ID: 13260236
Same version got AC
I am getting NZEC only when I try to read all the input at once.

ashish kumar: 2014-09-09 16:09:21

giving TLE please help
ID:12336742

aayush ojha: 2014-07-26 19:45:34

AC in a go :)
simple problem,just a bit of maths.

Last edit: 2014-07-26 19:45:49
Bruce Wayne: 2014-07-16 10:19:41

sir,
What's wrong in submission id : 11956601

Edit(Nishant):- In 78th line check it use different function it will overflow for big test cases.

Thanks Sir !

Last edit: 2014-07-16 16:35:48
Raja Singla: 2014-07-16 06:50:40

@Nishant, c u check #11955896, #11955817

Edit(Nishant):- first try how to find mod inverse then try it again

Last edit: 2014-07-16 15:41:16

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