Frank Underwood is on his way to find the President's book of Secrets kept inside a safe in the library at White House. The only way to open the safe is by entering a secret code obtained by calculating:

(a^b ÷ k) modulus M

M is a constant with value 10⁹+7.

Frank also has the value of k.

a and b can be found out by deciphering the given pattern inside the library that is each book in the library has a number written on it say R_i and S is a number formed by adding the numbers written on each book in the library. First two digits of S represent a and last two digits of S represent b. In case S is a one digit number then the secret code is -1. Frank gives you the number R_i written on each book and a number k. Your task is to find the secret code using the given information as quickly as possible.

Input format

First line contains an integer T representing number of test cases.

First line of each test case contains two space separated integers N(number of books) and k

Second line of each test case contains N space separated integers, the number written on each book.

Output format

For each test case, Output the secret code in different line using the above information.

Constraints

1 <= T <= 100

1 <= N <= 10⁴

1<= k <= 10³

0 <= R_i <= 10⁴