LASTDIG2

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

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int lastDig(int n, unsigned long long b) {  
    if (b == 0) {
        return 1;
    } else if (n == 0 || n == 1 || n == 5 || n == 6) {
        return n;
    }
    vector<int> ld;
    ld.push_back(n);
    int count = 0;
    do {
        ++count;
        ld.push_back((n*ld.back()) % 10);
    } while (ld.back() != n);
    int c = b % count - 1;
    if (c < 0) {
        c += count;
    }
    return ld[c];
}

int main() {  
    int t;
    cin >> t;
    for (;t--;) {
        string a;
        unsigned long long b;
        cin >> a >> b;
        int n = a[a.size() - 1] - '0';
        cout << lastDig(n, b) << "\n";
    }
    return 0;
}