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