import java.math.*;
import java.io.*;
import java.util.*;
class Main{
	
	
	public static void main(String args[]){
		Scanner cin =  new Scanner(System.in);
		int k =1;
		BigInteger a,b;
		int t= cin.nextInt();
		BigInteger two = new BigInteger("2");
		while(t--!=0){
			a = cin.nextBigInteger();
			b = cin.nextBigInteger();
			System.out.println("Scenario #"+k+":");
			k++;
	if(a.modPow(b.add(BigInteger.ONE.negate()).divide(two), b).compareTo(BigInteger.ONE)==0)
		    	System.out.println("1");
		    else
		    	System.out.println("-1");
	System.out.println();
		}
	}
	
}