/**********************************************************************
 * 
 * Remember how we learned to divide when we were kids? Let's divide
 * 3 by 7 in base 10:
 * 
 *     3 : 7 = 0.4285714...
 *    -0
 *    ==
 *     30   <--------------------+
 *    -28                         €
 *    ===                          €
 *      20                          €
 *     -14                           €
 *     ===                            €
 *       60                            €
 *      -56                             €
 *      ===                              €
 *        40                              €
 *       -35                               €
 *       ===                                €
 *         50                                €
 *        -49                                 €
 *        ===                                  €
 *          10                                  €
 *         - 7                                   €
 *         ===                                    €
 *           30   <--- Whoops, we've seen this already
 *          -28
 *          ===
 *            20
 * 
 * See what happens? As soon as we reach the remainder 30 (actually 3)
 * again, we will of course repeat over and over again what we've done
 * since first seeing it.
 * 
 * This solution simply remembers the point of time when we have seen
 * a remainder for the first time:
 * 
 *     first[rem] := Number of the first round we've seen this
 *                   remainder, and zero if we haven't seen it yet.
 * 
 * So we iterate over the remainders (by multiplying it with the base
 * and the "modulizing" it with the denominator) and as soon as we
 * see a remainder for the second time, we stop and subtract the round
 * number of the first occurence from the current round number. The
 * special case of a "zero period" can easily be detected, since we'll
 * just end up with a remainder of zero.
 * 
 * Just one more thing. You might have noticed it, but I didn't when
 * I saw/solved this problem for the first time and many others didn't
 * notice it, either. We all just solved it. In the above discussion
 * I quietly assumed that a repetition in the remainders is equivalent
 * to a repetition in the base expansion (i.e. in 0.4285714...). This
 * is in fact true, but not that obvious to see. However, as mentioned
 * already, my experience is that people just intuitively assume this,
 * which turns out not to be a problem.
 *
 **********************************************************************/

import java.io.*;

public class etpisa {
    public static void main ( String[] args ) throws Exception {
	BufferedReader in = new BufferedReader( new InputStreamReader( System.in ));
	int S = Integer.parseInt( in.readLine() );
	for( int s=1; s<=S; s++ ){
	    System.out.println( "Scenario #" + s + ":" );
	    
	    //--- Read scenario.
	    String[] line = in.readLine().split( " " );
	    int base = Integer.parseInt( line[0] );
	    int num = Integer.parseInt( line[1], base );
	    int den = Integer.parseInt( line[2], base );
	    
	    //--- Dance...
	    int[] first = new int[den];
	    int rem = num % den;
	    int round = 1;
	    while( first[rem] == 0 ){
		first[rem] = round;
		rem = rem * base % den;
		round++;
	    }
	    
	    //--- Answer.
	    System.out.println( (rem == 0) ? 0 : round - first[rem] );
	    System.out.println();
	} 
    }
}
