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
2016-10-25 13:26:16
Same as LASTDIG. Just the difference is that there are 1000 digits in a and for b use long long int .
Base is a number with maximum 1000 digits !!
Dont Think it's a number with maximum 1000 value .


2016-08-07 21:39:15 Himanshu Sharma
easy one.....silly mistakes are not so silly :-|
2016-07-17 03:00:20
I think this problem don't use multiplication with big numbers.
2016-06-27 10:18:57
o(1) ... slight modification in LASTDIG code...AC :)
2016-06-23 16:10:53
read base in char Array and index in long long int
AC in One GO!!!
2016-06-13 21:51:31
Same as LASTDIG. Just the difference is that there are 1000 digits in a .

Last edit: 2016-06-13 21:51:46
2016-06-12 07:24:05
if it says , 700 byte limit , your code too long - > then you could stack statements side by side to meet the 700 byte limit!! got ac with java !!
2016-05-29 14:55:03
@fly_sky12 Do not use bits/stdc++ . Then remove all white spaces(indentation,blank lines etc). Define one-character macros for frequently used keywords such as break,endl etc and replace them in the text. Use only one character for identifier names. These measures worked for me.
BTW, can anyone tell me why this restriction on file size is imposed?
2016-05-18 13:40:04
source limit is 700 bytes
my code is of more than this size.
plz give some tips to overcome it

Last edit: 2016-05-18 14:58:31
2016-04-22 03:54:24
@prateekmathur1991
If you try to read base into an integer or long you will get NZEC.
base can be 1000 digits !
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.