LASTDIG - The last digit

Nestor 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 him two numbers a and b. The problem consist of finding the last digit of the potency of base a and index b. Help Nestor with his problem. You are given two integer numbers: the base a (0 <= a <= 20) and the index b (0 <= b <= 2,147,483,000), a and b both are not 0. You have to find the last digit of ab.

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:
2
3 10
6 2

Output: 9 6

Added by:Jose Daniel Rodriguez Morales
Date:2008-12-01
Time limit:1s
Source limit:700B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:Own

hide comments
2016-07-22 02:42:28
my 10th..if you r using the pattern then be careful with %0..
2016-07-09 22:23:05
WA. tried every case :'(
2016-07-09 17:55:55
When unable to debug your code, create a brute force solution and test your solution against that for feasible test cases.
2016-07-04 19:45:48
Very very good problem. * spoiler* don't just use b%4.... Costed me 4WAs
2016-06-27 10:13:47
no modular exponentiation required... just the pattern ;)
2016-06-21 16:06:21 jayant choudhary
there is no need for any modular exponentiation technicque or any technicque ...it's very simple problem .. :)
it can be done in only 2 lines code ... see the pattern and there u go ;)
2016-06-16 18:16:12
Wtf! Tried everything and checked every test case but still shows wrong answer.... Help me someone....
100 0-1
0 50-0
10 159-0
1000 0-1
1000 1-0
Anything else.....
2016-06-13 21:09:59
Use Exponential squaring for finding the power.
2016-06-09 17:19:52
there is a possibility of an even faster algorithm. See for pattern in first digit after exponentiation with increasing n :)
2016-06-05 23:21:09
wow!! learned a new way of solving, had to change algo 2 times to get to the answer in given constraints .
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.