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

hide comments
cubalgo: 2016-07-22 02:42:28

my 10th..if you r using the pattern then be careful with %0..

vaibhavahuja: 2016-07-09 22:23:05

WA. tried every case :'(

saurabh2561: 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.

xinnix: 2016-07-04 19:45:48

Very very good problem. * spoiler* don't just use b%4.... Costed me 4WAs

adi_1996: 2016-06-27 10:13:47

no modular exponentiation required... just the pattern ;)

jayant choudhary: 2016-06-21 16:06:21

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 ;)

xinnix: 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.....

kp1994: 2016-06-13 21:09:59

Use Exponential squaring for finding the power.

kr_abhinav: 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 :)

v_ns: 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 .


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