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.


hide comments
kolahzary: 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 !

kolahzary: 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
vikash1143: 2016-03-09 05:56:10

Done in O(n/4)..0.02..!!!

akazad133032: 2016-02-21 08:42:02

Hey,,, it's a pattern .... :-) :-)

akash : 2016-01-26 18:49:02

Never mix 'scanf' and 'cin' when synchronization is turned off! Lesson learned!

prateekmathur1991: 2016-01-12 13:22:14

Runs fine on my PC, and ideone as well, but shows NZEC after submitting on SPOJ....!!!

dokz: 2016-01-06 10:56:10

Yay! 650 bytes in C# :)

sarthak_8: 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

DEVVRAT GUPTA: 2015-12-22 07:55:42

Please don't use bits/stdc++ header here as the limit is 700 bytes only...

AASHISH KUMAR: 2015-12-22 06:41:39

2 WA for long long int :(
Modular Exponentiation _/\_


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