Background

递归是个好东西。

Description

请求出2017^x的最后一位。（x的长度不会超过200）

Format

Input

第一行为正整数t，代表有t组数据（t<=200），第二行共有t个正整数x（0<=x<=10^12）。

Output

一个正整数，表示2017^x的最后一位。

Sample 1

Input

3
66 233 748

Output

9
7
1

Hint

可以分治。