Peter Parker, your friendly neighborhood Spider-man, attends college in mornings and at night he saves the city from dangerous villains.

He is currently studying large numbers in his Math class. For his homework, he needs to find the exponential of a sequence of positive integers. Exponential of a sequence of N integers is defined as follows -

1. If N is 1, the exponential is equal to the only integer in the sequence.
2. Otherwise, exponential is given by the left most integer raised to the power of the exponential of the remaining sequence of N-1 integers.

Given a sequence of N integers, he needs to find the last digit of its exponential.

For example: If the sequence is a, b, c, d, exponential is given by:

For the sequence 2, 2, 3, exponential is

2²³ = 2⁸ = 256. Its last digit is 6.

But today he got an emergency call from his Avenger teammates to protect the city from aliens. Can you help him do his homework while he saves the world?

Input: First line of the input contains T, the number of test cases. For each test case, there is a single line containing N+1 space separated integers where the first number represents N and the i+1 th number represents A_i.

Output: For each test case, print the last digit of the exponential of the sequence as explained in problem statement.

Constraints

1<=T<=100

1<= N <= 10000

1<= A_i (each integer in the sequence) <= 100000