Background

It is dark at night.
It is silence at night.
It is she in the dark.
It is she in the silence.

Then a light appeared. A huge gate came into our sights, called

The Gate to Freedom

Problem

There're some words on the gate: "This gate will lead you to freedom. First, you have to open it. I have a problem for you to solve, if you answer it correctly, the gate will open!"

"Tell me, young boy, what is the leftmost digit of N^N?"

This problem contains multiple test cases.

Each test case contains an integer N (N<=1,000,000,000).

For each test case, output the leftmost digit of N^N.