Once, a very smart guy who was able to do any arithmetic operation with big numbers had his brother kidnapped. However the kidnappers didn't wanted money for returning his brother but wanted him to answer a math question because they needed it ( nobody knows why :O ) , the problem they gave to him had a simple question , find the last digit of the given expression.

Input

On the first line there is number T <=50 the  number of test cases, then every test case has a single line which contains the expression, the length of the expression is no more than 1000 and the operations are not prioritized which means that you need to do the operations in the order they are given, but for making it more difficult kidnappers added some random symbols in the expression , you need to ignore them . It is guaranted that all the numbers are integers and there will be only 3 arithmetic operations + - and *.

Output

Exactly T lines each represetning the last digit of the expression.

Example

Input:
2

123n*11

12*njkm2

Output:
3

4