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.


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

hide comments
2018-01-07 10:56:46 Michael Kharitonov
@diptark_bose: EOL was converted to CRLF, use "Choose file" to prevent this from happening.

Last edit: 2018-01-07 10:57:07
2018-01-05 06:00:44
My source code is an exact 697 characters (which is <700 bytes). Still getting "Exceeding 700 bytes error"!!
2018-01-01 06:50:39
don't forget if b can be 0..
cost me much WA.. :(
2017-12-19 14:25:21
What should be the output of
1
0 0
2017-09-26 16:43:59
how to store b?
it is greater than the range of long long int.
2017-09-03 16:22:37
Very easy.....................................
AC in a go....
2017-07-07 12:48:06 vi1
Submitted _the same_ source as for LASTDIG. AC. What's the point?
2017-06-24 20:07:33 Anand Kumar
Happy to get AC. Third time... misread question
2017-05-31 11:47:46 Jamil Siam
Bigger constraints: http://www.spoj.com/problems/LSTDGT/
2017-05-05 10:41:01
Completely forgot a had 1000 digits :p costed 3 WA and lot of frustration
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.