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-04-22 02:54:04
Simple mistake in understanding the problem actually ate my day :|
Base is a number with maximum 1000 digits !!
I thought it's a number with maximum 1000 value :|

Plz don't repeat my mistake

Last edit: 2016-04-22 03:46:09
2016-03-09 05:56:10
Done in O(n/4)..0.02..!!!
2016-02-21 08:42:02
Hey,,, it's a pattern .... :-) :-)
2016-01-26 18:49:02 akash
Never mix 'scanf' and 'cin' when synchronization is turned off! Lesson learned!
2016-01-12 13:22:14 prateekmathur1991
Runs fine on my PC, and ideone as well, but shows NZEC after submitting on SPOJ....!!!
2016-01-06 10:56:10
Yay! 650 bytes in C# :)
2016-01-04 19:50:52
Got an AC finally after 4 WA. Don't know why it was giving WA when I took b in a string. Later taking b as LLI gave an AC. The code isn't long. I managed to get an AC with a code of 373B
2015-12-22 07:55:42 DEVVRAT GUPTA
Please don't use bits/stdc++ header here as the limit is 700 bytes only...
2015-12-22 06:41:39 AASHISH KUMAR
2 WA for long long int :(
Modular Exponentiation _/\_
2015-12-18 19:48:06 Robin Chawla
"Your solution is too long for this problem, the limit is 700 bytes! " how to remove this error plezz help!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.