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¹⁸) and P (2<=P<=10⁹).

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.