You are given a string \(S\) of length \(N\) which consists of digits from 0 to 9. You need to find an index \(i\) such that the sub number formed by \(S[i..N]\) is divisible by \(K\) and the xor of all the digits in the sub number formed by \(S[1..(i-1)]\) is maximum. If there are multiple \(i's\) such that \(S[i..N]\) is divisible by \(K\) and for all such values of \(i\), \(S[1..(i-1)]\) is maximum, then print the largest sub number.

(For example: If the string is 611234, then for i = 2, two sub number will be [6], [11234] and for i = 3, two sub number will be [61], [1234], for i = 4, two sub number will be [611], [234] and so on. So you have to select \(i\) such that 2nd sub number should be divisible by a given integer \(K\), and bitwise xor of all the digits of the 1st sub number is maximum. If there multiple \(i\) then print the largest 2nd sub number.)

The sub number \(S[i..N]\) should not contain any leading zeros and the value of \(S[i..N]\) should not be \(0\). Both the sub numbers \(S[1..(i-1)]\) and \(S[i..N]\) should contain at least one digit. If no answer exists, print \(-1\).

Input format

• First line: \(T\) denoting the number of test cases
• For each test case:
  • First line: Two space-separated integers \(N\) and \(K\)   
  • Second line: String \(S\)

Output format

If an answer exists, then print the sub number \(S[i..N]\). Otherwise, print \(-1\).

For each test case, print the answer in a new line.

Constraints

\(1 \le T \le 10\)

\(1 \le N \le 10^{5}\)

\(1 \le K \le 10^{9}\)