Cho 2 số N và M

Bạn hãy giúp Han tìm chữ số đầu tiên của $N^M$ nhé.

Input

Dòng đầu là số bộ kiểm thử $t(1\le t\le 1000)$

Các dòng tiếp theo gồm $t$ dòng mỗi dòng chứa hai số N (1 <= N <= 100), M (1 <= M <= 10^6)

Output

Gồm $t$ dòng mỗi dòng chứa chữ số đầu tiên của $N^M$ nhé.

VD

Input:

2
3 5
2 12

Output:

2
4

Giải thích

$3^5=243$ nên chữ số đầu tiên là 2

$2^{12}=4096$ nên chữ số đầu tiên là 4