Chef has called on you many times in the past to solve unusual tasks that seem irrelevant to cooking, and today is no different. Today Chef demands that you find integers whose product of digits is equal to a given integer, but in bases besides 10. Given a string S, you are to determine the smallest positive integer I such that there exists a base B>1 for which the product of the digits of I gives the integer represented by S. For example, if S="11", then the smallest I is 8, because the base 3 representation of I is 22, and in base 3 2*2=11.

Now that Chef has streamlined his cupcake baking procedure, he's turning his attention toward frosting the cupcakes. He recently purchased a machine that produces frosting. Each cupcake requires one unit of frosting, and the frosting machine requires K² units of energy to produce K units of frosting in one minute (K need not be an integer). Cupcakes arrive in batches, once per minute, needing frosting. The cupcakes must be frosted within a minute of when they arrive. The frosting machine also has a reserve unit, so it can produce extra frosting to be used later.

For a given prime number p find the number of all pairs (m, n) of positive integers such that 1 <= m, n <= p*(p-1) and p divides n^m - mⁿ. Output the result modulo 1000000007.

Input

The first line contains a single positive integer T <= 100, the number of test cases. T test cases follow. The only line of each test case contains a prime number p , where 2 <= p <= 10¹².

After recent success of cooking reality shows, Chef decided to borrow the idea and host his own "Devil's Kitchen" show. But his ambitions are even bigger. He plans to build a whole complex of hotels, gyms and other entertainment facilities along with one main restaurant where he'll host the show. But first of all, he needs to purhase some land to build on. The country is divided into a grid with R rows and C columns of smaller parcels. Chef wants to buy a rectangular piece of land H parcels high and W parcels wide. He also has a preferred layout in mind.