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<=10^{18}) and P (2<=P<=10^{9}).
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:
20150905 17:18:28
easy one 

Shashank Tiwari:
20150712 11:14:12
Just consider Gcd and try to prove why it will be 1. 

newbie:
20150610 13:57:15
easy one...no tricky cases 

Raghav Aggiwal Again:
20150116 18:03:58
Forgetting a newline at the end of output caused me 7 wa.. :(


Abhishek:
20141225 09:36:40
NZEC error , please check my submission 

Vamsi Krishna Avula:
20141225 06:51:48
Nishant Raj sir, can you please tell me why code is getting NZEC? ID: 13260236


ashish kumar:
20140909 16:09:21
giving TLE please help


aayush ojha:
20140726 19:45:34
AC in a go :)


Bruce Wayne:
20140716 10:19:41
sir,


Raja Singla:
20140716 06:50:40
@Nishant, c u check #11955896, #11955817

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