#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

ull base ;
string a ;

map < char , ull > w ;
map < char , int > hh ;
bool used[ 36 ] ;

void solve ( ) {
    cin >> base >> a ;
    ull ans = 0 ;
    ull coef = 1 ;
    int n = a.size ( ) ;
    w.clear ( ) ;
    for ( int i = n - 1 ; i >= 0 ; -- i ) {
        w[ a[ i ] ] += coef ;
        coef *= base ;
    }
    if ( base == 2 ) {
        cout << w[ a[ 0 ] ] << "\n" ;
        return ;
    }
    for ( int i = 0 ; i < n ; ++ i ) {
        if ( hh.find ( a[ i ] ) != hh.end ( ) ) { continue ; }
        for ( int j = 0 ; j < base ; ++ j ) {
            if ( j == 0 && i == 0 ) { continue ; }
            if ( used[ j ] == true ) { continue ; }
            hh[ a[ i ] ] = j ;
            used[ j ] = true ;
            break ;
        }
    }
    for ( auto [ c , sm ] : w ) {
        ans += sm * hh[ c ] ;
    }    
    if ( (int)w.size ( ) < base ) { w[ '#' ] = 0 ; }
    for ( auto [ c1 , v1 ] : w ) {
        for ( auto [ c2 , v2 ] : w ) {
            if ( c1 == c2 ) { continue ; }
            if ( v1 > v2 ) { 
                ans = __gcd ( ans , v1 - v2 ) ;
            }
        }
    }
    cout << ans << "\n" ;
}

int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}