E. Again Last Digit
time limit per test
1 second
memory limit per test
128 megabytes
input
standard input
output
standard output

$$$n!$$$ is factorial of $$$n$$$.

$$$f_n$$$ is $$$n$$$-th fibonacci number.

$$$f_0$$$ $$$=$$$ $$$0$$$

$$$f_1$$$ $$$=$$$ $$$1$$$

$$$f_n$$$ $$$=$$$ $$$f_{n - 1}$$$ + $$$f_{n - 2}$$$

You are given an integer $$$n$$$.

$$$S = f_0^{0!} + f_1^{1!} + f_2^{2!} + f_3^{3!} + \dots + f_n^{n!}$$$

In other words, sum of $$$f_i$$$ power of $$$i!$$$

Your task is to find the last digit of $$$S$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$0 \le n \le 10^{18}$$$).

Output

For each test case, output a single integer.

Example
Input
3
4
87
4619
Output
7
8
4