SP8277 PSTR - Number of Prime Strings

A string is called a "prime string" if it can't be written as concatenation of more than one same strings. For example, the following strings are not prime strings: AAA, ABABAB, CFGFGCFGFG, while CFGFGC, ABABA are prime strings. Calculate the number of prime string of length N (1

Multiple test cases. The number of them (about 10000) is given in the very first line. Each test case contains one line with two integers - K and N, seperated by a single space.

For each test case, output the required number modulo 1000000007 in a single line. Example ``` Input: 1 2 3 Output: 6 Explanation The prime strings of length 3 which only contain character 'A' and 'B' are: AAB,ABA,ABB,BAA,BAB,BBA. ```