B. Omar's Magic Trick
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Omar and Ahmed are playing with an infinite deck of cards. Each card has a single-digit number written on it (ranging from $$$1$$$ to $$$9$$$).

Ahmed teaches Omar a new trick. Here are the steps:

  1. Initial Selection:
    • Omar selects three cards from the deck.

  2. Transformation:
    • Ahmed instructs Omar to multiply the value of each selected card by $$$3$$$.
    • Omar then replaces each card with the digits of the result. For example, if the original card value is $$$8$$$, Omar replaces it with two cards: $$$2$$$ and $$$4$$$.
    • Omar repeats this transformation a total of n times.

  3. Final Choice:
    • After all the transformations, Omar chooses a card from the last set of cards (the result of the $$$n_{th}$$$ transformation) and hides it.

Given the remaining cards in the deck (after all transformations) except the hidden card, can you determine the hidden one?

It is guaranteed that the answer always exists

The order of the number is not important, for example the $$$[1$$$ $$$8$$$ $$$1$$$ $$$5$$$ $$$6$$$ $$$2$$$ $$$1]$$$ and $$$[1$$$ $$$8$$$ $$$1$$$ $$$5$$$ $$$6$$$ $$$1$$$ $$$2]$$$ give the same answer which is $$$3$$$

Input

The first line contains one integer number $$$(1 \le T \le 10^4)$$$, the number of test cases.

The first line of each test case contains $$$2$$$ integers $$$n, m$$$ $$$(2 \le n \le 33, 2 \le m \le 10^6)$$$.

The second line contains $$$m$$$ integers $$$a_1,a_2,..,a_m (1 \le a_i \le 9)$$$.

An additional constraint on the input: the sum of $$$m$$$ over all test cases doesn't exceed $$$10^6$$$.

It is guaranteed that the set of cards is always a valid set

Output

For each test case, print a single integer — The card Omar has hidden.

Example
Input
1
2 7
1 8 1 5 6 2 1
Output
3
Note

In the first test case:

  • The initial set is $$${2, 5, 9}$$$.
  • After the first operation, the set becomes $$${6, 1, 5, 2, 7}$$$.
  • After the second operation, the set becomes $$${1, 8, 3, 1, 5, 6, 2, 1}$$$.
  • Omar hides $$$3$$$.
  • So the remaining set is $$${1, 8, 1, 5, 6, 2, 1}$$$.