SP20562 TANDC - Tracy and Charlie

Tracy is teaching Charlie maths via a game called N-Cube, which involves three sections involving N. Tracy gives Charlie a number N, and Charlie makes a list of N $ ^{th} $ powers of integers in increasing order (1 $ ^{N} $ , 2 $ ^{N} $ , 3 $ ^{N} $ .. so on). This teaches him exponentiation. Then Charlie performs the following subtraction game N times : Take all pairs of consecutive numbers in the list and take their difference. These differences then form the new list for the next iteration of the game. Eg, if N was 6, the list proceeds as \[1, 64, 729, 4096 ... \] to \[63, 685, 3367 ...\], and so on 5 more times. After the subtraction game, Charlie has to correctly tell Tracy the Nth element of the list. This number is the _value of the game_. After practice Charlie became an expert in the game. To challenge him more, Tracy will give two numbers **M** (where M is a prime) and **R** instead of just a single number N, and the game must start from **M $ ^{R} $ - 1** instead of N. Since the _value of the game_ can now become large, Charlie just have to tell the largest integer K such that M $ ^{K} $ divides this number. Since even K can be large, output K modulo 1000000007 (10 $ ^{9} $ +7). **INPUT:** First line will contain **T**, number of testcases. Then the testcases follow Each testcase contains of a single line of input, two integers **M R** **OUTPUT:** For each testcase, output in a single line answer given by Charlie to Tracy modulo 1000000007. **CONSTRAINTS:** 1

N/A

N/A