#pragma GCC optimize ( "O3" )
#pragma GCC optimize( "unroll-loops" )
#pragma GCC target ( "sse4.2,fma,avx2,popcnt,lzcnt,bmi2" )
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdint.h>
#include <cassert>
using namespace std;

using ll = long long;

#define MAIN main
#define TYPE_OF( VAR ) remove_const<remove_reference<decltype( VAR )>::type >::type
#define CEXPR( LL , BOUND , VALUE ) constexpr const LL BOUND = VALUE 
#define CIN( LL , A ) LL A; cin >> A 
#define ASSERT( A , MIN , MAX ) assert( MIN <= A && A <= MAX ) 
#define CIN_ASSERT( A , MIN , MAX ) CIN( TYPE_OF( MAX ) , A ); ASSERT( A , MIN , MAX ) 
#define FOR( VAR , INITIAL , FINAL_PLUS_ONE ) for( TYPE_OF( FINAL_PLUS_ONE ) VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ )
#define REPEAT( HOW_MANY_TIMES ) FOR( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES )
#define QUIT return 0
#define COUT( ANSWER ) cout << ( ANSWER ) << "\n"
#define RETURN( ANSWER ) COUT( ANSWER ); QUIT

#define POWER( ANSWER , ARGUMENT , EXPONENT )				\
  TYPE_OF( ARGUMENT ) ANSWER{ 1 };					\
  {									\
    TYPE_OF( ARGUMENT ) ARGUMENT_FOR_SQUARE_FOR_POWER = ( ARGUMENT );	\
    TYPE_OF( EXPONENT ) EXPONENT_FOR_SQUARE_FOR_POWER = ( EXPONENT );	\
    while( EXPONENT_FOR_SQUARE_FOR_POWER != 0 ){			\
      if( EXPONENT_FOR_SQUARE_FOR_POWER % 2 == 1 ){			\
	ANSWER *= ARGUMENT_FOR_SQUARE_FOR_POWER;			\
      }									\
      ARGUMENT_FOR_SQUARE_FOR_POWER *= ARGUMENT_FOR_SQUARE_FOR_POWER;	\
      EXPONENT_FOR_SQUARE_FOR_POWER /= 2;				\
    }									\
  }									\

template <typename INT>
class QuotientRing
{

protected:
  INT m_n;
  const INT* m_p_M;

public:
  inline QuotientRing() noexcept;
  inline QuotientRing( const INT& n , const INT* const & p_M = nullptr ) noexcept;
  inline QuotientRing( const QuotientRing<INT>& n ) noexcept;

  inline QuotientRing<INT>& operator+=( const QuotientRing<INT>& n ) noexcept;
  inline QuotientRing<INT>& operator+=( const INT& n ) noexcept;
  // operator<が定義されていても負の数は正に直さず剰余を取ることに注意。
  inline QuotientRing<INT>& operator-=( const QuotientRing<INT>& n ) noexcept;
  inline QuotientRing<INT>& operator-=( const INT& n ) noexcept;
  inline QuotientRing<INT>& operator*=( const QuotientRing<INT>& n ) noexcept;
  inline QuotientRing<INT>& operator*=( const INT& n ) noexcept;

  inline const INT& Represent() const noexcept;
  inline const INT& GetModulo() const noexcept;

  // m_nの正負やm_p_Mの一致込みの等号。
  static inline bool Equal( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept;

  template <typename T> static QuotientRing<INT> Power( const QuotientRing<INT>& n , const T& exponent );
  
};

template <typename INT> inline bool operator==( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept;
template <typename INT> inline bool operator!=( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept;

template <typename INT , typename T> inline QuotientRing<INT> operator+( const QuotientRing<INT>& n0 , const T& n1 ) noexcept;
template <typename INT , typename T> inline QuotientRing<INT> operator-( const QuotientRing<INT>& n0 , const T& n1 ) noexcept;
template <typename INT , typename T> inline QuotientRing<INT> operator*( const QuotientRing<INT>& n0 , const T& n1 ) noexcept;

template <typename INT , typename T> inline QuotientRing<INT> Power( const QuotientRing<INT>& n , const T& exponent );


template <typename INT> inline QuotientRing<INT>::QuotientRing() noexcept : m_n() , m_p_M( nullptr ) {}
template <typename INT> inline QuotientRing<INT>::QuotientRing( const INT& n , const INT* const & p_M ) noexcept : m_n( p_M == nullptr ? n : n % *p_M ) , m_p_M( p_M ) {}
template <typename INT> inline QuotientRing<INT>::QuotientRing( const QuotientRing<INT>& n ) noexcept : m_n( n.m_n ) , m_p_M( n.m_p_M ) {}

template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator+=( const QuotientRing<INT>& n ) noexcept { if( m_p_M == nullptr ){ m_p_M = n.m_p_M; } m_n += n.m_n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator+=( const INT& n ) noexcept { m_n += n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator-=( const QuotientRing<INT>& n ) noexcept { if( m_p_M == nullptr ){ m_p_M = n.m_p_M; } m_n -= n.m_n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator-=( const INT& n ) noexcept { m_n -= n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator*=( const QuotientRing<INT>& n ) noexcept { if( m_p_M == nullptr ){ m_p_M = n.m_p_M; } m_n *= n.m_n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
template <typename INT> inline QuotientRing<INT>& QuotientRing<INT>::operator*=( const INT& n ) noexcept { m_n *= n; if( m_p_M != nullptr ){ m_n %= *m_p_M; } return *this; }
  
template <typename INT> inline const INT& QuotientRing<INT>::Represent() const noexcept { return m_n; }
template <typename INT> inline const INT& QuotientRing<INT>::GetModulo() const noexcept { static const INT zero{ 0 }; return m_p_M == nullptr ? zero : *m_p_M; }

template <typename INT> inline bool QuotientRing<INT>::Equal( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept { return n0.m_n == n1.m_n && n0.m_p_M == n1.m_p_M; }

template <typename INT> template <typename T>
QuotientRing<INT> QuotientRing<INT>::Power( const QuotientRing<INT>& n , const T& exponent )
{

  QuotientRing<INT> answer{ 1 , n.m_p_M };
  QuotientRing<INT> power{ n };

  while( exponent != 0 ){

    if( exponent % 2 == 1 ){

      answer *= power;

    }

    power *= power;
    exponent /= 2;

  }

  return answer;

}

template <typename INT> inline bool operator==( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept { return QuotientRing<INT>::Equal( n0 , n1 ); }
template <typename INT> inline bool operator!=( const QuotientRing<INT>& n0 , const QuotientRing<INT>& n1 ) noexcept { return ! QuotientRing<INT>::Equal( n0 , n1 ); }

template <typename INT , typename T> inline QuotientRing<INT> operator+( const QuotientRing<INT>& n0 , const T& n1 ) noexcept { return QuotientRing<INT>( n0 ).operator+=( n1 ); }
template <typename INT , typename T> inline QuotientRing<INT> operator-( const QuotientRing<INT>& n0 , const T& n1 ) noexcept { return QuotientRing<INT>( n0 ).operator-=( n1 ); }
template <typename INT , typename T> inline QuotientRing<INT> operator*( const QuotientRing<INT>& n0 , const T& n1 ) noexcept { return QuotientRing<INT>( n0 ).operator*=( n1 ); }

template <typename INT , typename T> inline QuotientRing<INT> Power( const QuotientRing<INT>& n , const T& exponent ) { return QuotientRing<INT>::template Power<T>( n , exponent ); }



template <typename INT>
class QuadraticExtension
{

private:
  INT m_a;
  INT m_b;
  const INT* m_p_D;
  
public:
  inline QuadraticExtension() noexcept;
  template <typename T> inline QuadraticExtension( const T& a ) noexcept;
  inline QuadraticExtension( const INT& a , const INT& b , const INT* const & p_D ) noexcept;
  inline QuadraticExtension( const QuadraticExtension<INT>& n ) noexcept;

  inline const INT& GetA() const noexcept;
  inline const INT& GetB() const noexcept;
  inline const INT& GetD() const noexcept;

  inline QuadraticExtension<INT>& operator+=( const QuadraticExtension<INT>& n ) noexcept;
  template <typename T> inline QuadraticExtension<INT>& operator+=( const T& a ) noexcept;
  inline QuadraticExtension<INT>& operator-=( const QuadraticExtension<INT>& n ) noexcept;
  template <typename T> inline QuadraticExtension<INT>& operator-=( const T& a ) noexcept;

  // 3数の乗法が入るのでオーバーフローに注意
  // 10^6より大きいmodで計算する時はINTにMod<M>などを代入するか乗法の定義を修正する
  inline QuadraticExtension<INT>& operator*=( const QuadraticExtension<INT>& n ) noexcept;
  template <typename T> inline QuadraticExtension<INT>& operator*=( const T& a ) noexcept;
  template <typename T> inline QuadraticExtension<INT>& operator/=( const T& a ) noexcept;
  template <typename T> inline QuadraticExtension<INT>& operator%=( const T& a ) noexcept;

  // m_p_Dの一致込みの等号
  static inline bool Equal( const QuadraticExtension<INT>& n0 , const QuadraticExtension<INT>& n1 ) noexcept;

private:
  static inline const INT& Zero() noexcept;
  
};

template <typename INT> inline bool operator==( const QuadraticExtension<INT>& n0 , const QuadraticExtension<INT>& n1 ) noexcept;
template <typename INT> inline bool operator!=( const QuadraticExtension<INT>& n0 , const QuadraticExtension<INT>& n1 ) noexcept;

template <typename INT , typename T> inline QuadraticExtension<INT> operator+( const QuadraticExtension<INT>& n , const T& a ) noexcept;
template <typename INT , typename T> inline QuadraticExtension<INT> operator-( const QuadraticExtension<INT>& n , const T& a ) noexcept;
template <typename INT , typename T> inline QuadraticExtension<INT> operator*( const QuadraticExtension<INT>& n , const T& a ) noexcept;
template <typename INT , typename T> inline QuadraticExtension<INT> operator/( const QuadraticExtension<INT>& n , const T& a ) noexcept;
template <typename INT , typename T> inline QuadraticExtension<INT> operator%( const QuadraticExtension<INT>& n , const T& a ) noexcept;

// Dは一時変数でない変数
template <typename INT> inline QuadraticExtension<INT> Sqrt( const INT& D ) noexcept;


template <typename INT> inline QuadraticExtension<INT>::QuadraticExtension() noexcept : m_a() , m_b() , m_p_D( nullptr ) {}
template <typename INT> template <typename T> inline QuadraticExtension<INT>::QuadraticExtension( const T& a ) noexcept : m_a( a ) , m_b() , m_p_D( nullptr ) {}
template <typename INT> inline QuadraticExtension<INT>::QuadraticExtension( const INT& a , const INT& b , const INT* const & p_D ) noexcept : m_a( a ) , m_b( b ) , m_p_D( p_D ) {}
template <typename INT> inline QuadraticExtension<INT>::QuadraticExtension( const QuadraticExtension<INT>& n ) noexcept : m_a( n.m_a ) , m_b( n.m_b ) , m_p_D( n.m_p_D ) {}

template <typename INT> inline const INT& QuadraticExtension<INT>::GetA() const noexcept { return m_a; }
template <typename INT> inline const INT& QuadraticExtension<INT>::GetB() const noexcept { return m_b; }
template <typename INT> inline const INT& QuadraticExtension<INT>::GetD() const noexcept { return m_p_D == nullptr ? Zero() : *m_p_D; }

template <typename INT> inline QuadraticExtension<INT>& QuadraticExtension<INT>::operator+=( const QuadraticExtension<INT>& n ) noexcept { if( m_p_D == nullptr ){ m_p_D = n.m_p_D; } m_a += n.m_a; m_b += n.m_b; return *this; }
template <typename INT> template <typename T> inline QuadraticExtension<INT>& QuadraticExtension<INT>::operator+=( const T& a ) noexcept { m_a += a; return *this; }
template <typename INT> inline QuadraticExtension<INT>& QuadraticExtension<INT>::operator-=( const QuadraticExtension<INT>& n ) noexcept { if( m_p_D == nullptr ){ m_p_D = n.m_p_D; } m_a -= n.m_a; m_b -= n.m_b; return *this; }
template <typename INT> template <typename T> inline QuadraticExtension<INT>& QuadraticExtension<INT>::operator-=( const T& a ) noexcept { m_a -= a; return *this; }
template <typename INT> inline QuadraticExtension<INT>& QuadraticExtension<INT>::operator*=( const QuadraticExtension<INT>& n ) noexcept { if( m_p_D == nullptr ){ m_p_D = n.m_p_D; } const INT a = ( m_p_D == nullptr ? m_a * n.m_a : m_a * n.m_a + m_b * n.m_b * ( *m_p_D ) ); m_b = m_a * n.m_b + m_b * n.m_a; m_a = a; return *this; }
template <typename INT> template <typename T> inline QuadraticExtension<INT>& QuadraticExtension<INT>::operator*=( const T& a ) noexcept { m_a *= a; m_b *= a; return *this; }
template <typename INT> template <typename T> inline QuadraticExtension<INT>& QuadraticExtension<INT>::operator/=( const T& a ) noexcept { m_a /= a; m_b /= a; return *this; }
template <typename INT> template <typename T> inline QuadraticExtension<INT>& QuadraticExtension<INT>::operator%=( const T& a ) noexcept { m_a %= a; m_b %= a; return *this; }

template <typename INT> inline bool QuadraticExtension<INT>::Equal( const QuadraticExtension<INT>& n0 , const QuadraticExtension<INT>& n1 ) noexcept { return n0.m_a == n1.m_a && n0.m_b == n1.m_b && n0.m_p_D == n1.m_p_D; }

template <typename INT> inline const INT& QuadraticExtension<INT>::Zero() noexcept { static const INT zero{ 0 }; return zero; }

template <typename INT> inline bool operator==( const QuadraticExtension<INT>& n0 , const QuadraticExtension<INT>& n1 ) noexcept { return QuadraticExtension<INT>::Equal( n0 , n1 ); }
template <typename INT> inline bool operator!=( const QuadraticExtension<INT>& n0 , const QuadraticExtension<INT>& n1 ) noexcept { return ! QuadraticExtension<INT>::Equal( n0 , n1 ); }

template <typename INT , typename T> inline QuadraticExtension<INT> operator+( const QuadraticExtension<INT>& n , const T& a ) noexcept { return QuadraticExtension<INT>( n ).operator+=( a ); }
template <typename INT , typename T> inline QuadraticExtension<INT> operator-( const QuadraticExtension<INT>& n , const T& a ) noexcept { return QuadraticExtension<INT>( n ).operator-=( a ); }
template <typename INT , typename T> inline QuadraticExtension<INT> operator*( const QuadraticExtension<INT>& n , const T& a ) noexcept { return QuadraticExtension<INT>( n ).operator*=( a ); }
template <typename INT , typename T> inline QuadraticExtension<INT> operator/( const QuadraticExtension<INT>& n , const T& a ) noexcept { return QuadraticExtension<INT>( n ).operator/=( a ); }
template <typename INT , typename T> inline QuadraticExtension<INT> operator%( const QuadraticExtension<INT>& n , const T& a ) noexcept { return QuadraticExtension<INT>( n ).operator%=( a ); }

template <typename INT> inline QuadraticExtension<INT> Sqrt( const INT& D ) noexcept { return QuadraticExtension<INT>( 0 , 1 , &D ); }

int MAIN()
{
  CEXPR( int , bound_T , 10000 );
  CIN_ASSERT( T , 1 , bound_T );
  CEXPR( ll , bound_NML , 1000000000000000000 );
  CEXPR( ll , bound_B , 1000000000 );
  REPEAT( T ){
    CIN_ASSERT( N , 1 , bound_NML );
    CIN_ASSERT( M_base , 1 , bound_NML );
    CIN_ASSERT( L_base , 1 , bound_NML );
    CIN_ASSERT( B , 1 , bound_B );
    QuotientRing<ll> M{ M_base , &B };
    QuadraticExtension<QuotientRing<ll> > L{ QuotientRing<ll>( L_base , &B ) , 0 , &M };
    QuadraticExtension<QuadraticExtension<QuotientRing<ll> > > sqrtM{ Sqrt<QuotientRing<ll> >( M ) };
    QuadraticExtension<QuadraticExtension<QuotientRing<ll> > > sqrtL = Sqrt<QuadraticExtension<QuotientRing<ll> > >( L );
    POWER( power , sqrtM + sqrtL , N );
    const QuadraticExtension<QuotientRing<ll> >& power_coeff = N % 2 == 0 ? power.GetA() : power.GetB();
    COUT( power_coeff.GetA().Represent() );
  }
  QUIT;
}