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

code1monkey1: 2016-06-02 15:10:47

spoj is giving error while submitting as it says that the solution takes more than 700 bytes ,
what to do :/

coderaashir: 2016-05-30 14:46:39

It says 0 <= b and a so they can be equal.

manish3749: 2016-05-25 23:00:34

awesome one... must solve....accepted in first go

avisheksanvas: 2016-05-18 11:41:08

https://crypto.stanford.edu/pbc/notes/numbertheory/exp.html
Best explanation of Modular Exponentiation :).
Recursion with base case (b==0)

Last edit: 2016-05-18 11:41:39

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