LASTDIG2 - The last digit re-visited


Pappu was doing the work of his math class about three days but he is tired of make operations a lot and he should deliver his task tomorrow. His math’s teacher gives two numbers a and b. The problem consist in find the last digit of the potency of base a and index b. Help Pappu with his problem. You are given two integer numbers: the base a (number of digits d, such that 1 <= d <= 1000) and the index b (0 <= b <= 922*10^15). You have to find the last digit of a^b.

Input

The first line of input contains an integer t, the number of test cases (t <= 30). t test cases follow. For each test case will appear a and b separated by space.

Output

For each test case output an integer per line representing the result.

Example

Input:
3
3 10
6 2
150 53

Output:
9
6
0

Source limit is 700 Bytes.


hide comments
Zed: 2015-02-08 15:22:21

variable (string) which stores the base has to have length longer than 101, this has cost me 2WA. Also, exponent easily fits into long long unsigned.

Sajan mishra: 2015-02-05 11:02:27

Thanks @Abhinandan Agarwal !!

Shankar Chaudhary: 2015-01-26 11:02:07

finally AC :) thank you @abhinandan and @thramas

catnip123: 2015-01-21 21:01:49

long long doesnt work

thramas: 2015-01-20 21:02:47

Use strlen

Abhinandan Agarwal: 2015-01-09 11:56:03

Test the following test case :
2
100 100
100 0
Output should be
0
1
....
This may give wrong answer if you read both numbers into a string

agaurav77: 2014-12-13 18:16:13

Read the problem very carefully. The base can have upto 1000 digits (might be interpreted differently) and the exponent will fit into long long. AC!

(Tjandra Satria Gunawan)(曾毅昆): 2013-04-11 16:21:32

warning: there are '\r' character in the input data!
edit: and no '\r' or '\n' in the last case, how bad the input data...

Last edit: 2013-04-11 16:25:19

Added by:Hari
Date:2009-12-27
Time limit:1s
Source limit:700B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:harrydcoder