#include <iostream>
#include <string>
#include <sstream>
#include <math.h>
#include <iomanip>
 
using namespace std;
 
long long int a, b, r; int dlugosc; int ile;
 
int main()
{
cin >>  ile;
for (int i=1; i<=ile; i++)
{
    cin >> a >> b;
 
    if ((b>4)&&(b%4!=0)) {r=b%4;}
    if (b%4==0) {r=4;}
    else r=b;
 
   ostringstream ss;
   ss << setprecision (1000000000)<<pow(a,r);
   string str = ss.str();
   dlugosc=str.length();
 
 
    cout <<str.erase(0,dlugosc-1)<<endl;
    }
 
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPG1hdGguaD4KI2luY2x1ZGUgPGlvbWFuaXA+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKbG9uZyBsb25nIGludCBhLCBiLCByOyBpbnQgZGx1Z29zYzsgaW50IGlsZTsKCmludCBtYWluKCkKewpjaW4gPj4gIGlsZTsKZm9yIChpbnQgaT0xOyBpPD1pbGU7IGkrKykKewogICAgY2luID4+IGEgPj4gYjsKCiAgICBpZiAoKGI+NCkmJihiJTQhPTApKSB7cj1iJTQ7fQogICAgaWYgKGIlND09MCkge3I9NDt9CiAgICBlbHNlIHI9YjsKCiAgIG9zdHJpbmdzdHJlYW0gc3M7CiAgIHNzIDw8IHNldHByZWNpc2lvbiAoMTAwMDAwMDAwMCk8PHBvdyhhLHIpOwogICBzdHJpbmcgc3RyID0gc3Muc3RyKCk7CiAgIGRsdWdvc2M9c3RyLmxlbmd0aCgpOwoKCiAgICBjb3V0IDw8c3RyLmVyYXNlKDAsZGx1Z29zYy0xKTw8ZW5kbDsKICAgIH0KCiAgICByZXR1cm4gMDsKfQo=