Assi is really good at Idockady. According to urban dictionary it means :

Fascinating intellectual breakthroughs regarding reality, language, existence, knowledge, perception, or human behavior which are completely unprovable and utterly without use, and therefore of no real consequence to anyone.

One day Gopesh asked Assi to solve one question : Given N numbers where some or all numbers are divisible by 5. Find the product of all the numbers and print the last digit. Help Assi to prove Gopesh that he is not Idockad.

Input

The first line of the input contains a single integer T (1 ≤ T≤ 100) — the number of test cases.

Each test case starts with a single containing a single integer N (1 <= N <= 10^5).

Then in the next line contains N integers. a1, a2, a3, ...., an (1<= ai <= 10^6)

Output

Print T lines. In each line print a single integer.