/*
 * Solution by Alex w/r/t Fabian Gundlach
 * On Windows, build with VS2015
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

using namespace std;

const int N = 1000000007;
const int P = 14;

const int primes[] = {
      2,     3,     5,     7,    11,    13,    17,    19,    23,    29, 
     31,    37,    41,    43,    47,    53,    59,    61,    67,    71, 
     73,    79,    83,    89,    97,   101,   103,   107,   109,   113, 
    127,   131,   137,   139,   149,   151,   157,   163,   167,   173, 
    179,   181,   191,   193,   197,   199,   211,   223,   227,   229, 
    233,   239,   241,   251,   257,   263,   269,   271,   277,   281, 
    283,   293,   307,   311,   313,   317,   331,   337,   347,   349, 
    353,   359,   367,   373,   379,   383,   389,   397,   401,   409, 
    419,   421,   431,   433,   439,   443,   449,   457,   461,   463, 
    467,   479,   487,   491,   499,   503,   509,   521,   523,   541, 
    547,   557,   563,   569,   571,   577,   587,   593,   599,   601, 
    607,   613,   617,   619,   631,   641,   643,   647,   653,   659, 
    661,   673,   677,   683,   691,   701,   709,   719,   727,   733, 
    739,   743,   751,   757,   761,   769,   773,   787,   797,   809, 
    811,   821,   823,   827,   829,   839,   853,   857,   859,   863, 
    877,   881,   883,   887,   907,   911,   919,   929,   937,   941, 
    947,   953,   967,   971,   977,   983,   991,   997,  1009,  1013, 
   1019,  1021,  1031,  1033,  1039,  1049,  1051,  1061,  1063,  1069, 
   1087,  1091,  1093,  1097,  1103,  1109,  1117,  1123,  1129,  1151, 
   1153,  1163,  1171,  1181,  1187,  1193,  1201,  1213,  1217,  1223, 
   1229,  1231,  1237,  1249,  1259,  1277,  1279,  1283,  1289,  1291, 
   1297,  1301,  1303,  1307,  1319,  1321,  1327,  1361,  1367,  1373, 
   1381,  1399,  1409,  1423,  1427,  1429,  1433,  1439,  1447,  1451, 
   1453,  1459,  1471,  1481,  1483,  1487,  1489,  1493,  1499,  1511, 
   1523,  1531,  1543,  1549,  1553,  1559,  1567,  1571,  1579,  1583, 
   1597,  1601,  1607,  1609,  1613,  1619,  1621,  1627,  1637,  1657, 
   1663,  1667,  1669,  1693,  1697,  1699,  1709,  1721,  1723,  1733, 
   1741,  1747,  1753,  1759,  1777,  1783,  1787,  1789,  1801,  1811, 
   1823,  1831,  1847,  1861,  1867,  1871,  1873,  1877,  1879,  1889, 
   1901,  1907,  1913,  1931,  1933,  1949,  1951,  1973,  1979,  1987, 
   1993,  1997,  1999,  2003,  2011,  2017,  2027,  2029,  2039,  2053, 
   2063,  2069,  2081,  2083,  2087,  2089,  2099,  2111,  2113,  2129, 
   2131,  2137,  2141,  2143,  2153,  2161,  2179,  2203,  2207,  2213, 
   2221,  2237,  2239,  2243,  2251,  2267,  2269,  2273,  2281,  2287, 
   2293,  2297,  2309,  2311,  2333,  2339,  2341,  2347,  2351,  2357, 
   2371,  2377,  2381,  2383,  2389,  2393,  2399,  2411,  2417,  2423, 
   2437,  2441,  2447,  2459,  2467,  2473,  2477,  2503,  2521,  2531, 
   2539,  2543,  2549,  2551,  2557,  2579,  2591,  2593,  2609,  2617, 
   2621,  2633,  2647,  2657,  2659,  2663,  2671,  2677,  2683,  2687, 
   2689,  2693,  2699,  2707,  2711,  2713,  2719,  2729,  2731,  2741, 
   2749,  2753,  2767,  2777,  2789,  2791,  2797,  2801,  2803,  2819, 
   2833,  2837,  2843,  2851,  2857,  2861,  2879,  2887,  2897,  2903, 
   2909,  2917,  2927,  2939,  2953,  2957,  2963,  2969,  2971,  2999, 
   3001,  3011,  3019,  3023,  3037,  3041,  3049,  3061,  3067,  3079, 
   3083,  3089,  3109,  3119,  3121,  3137,  3163, 0
};

int gcd(int64_t a, int64_t b) {
  while(1) {
    if(!b) return a;
    a %= b;
    if(!a) return b;
    b %= a;
  }
}

int modinv(int n, int n_) {
  int t = 1, t_ = 0, qm1, orig_n_ = n_;
  while(n_ % n) {
    qm1 = n_/n - 1;
    t_ -= qm1*t; t = t_ - t; t_ -= t;
    n_ -= qm1*n; n = n_ - n; n_ -= n;
  }
  return (t >= 0) ? t : t+orig_n_;
}

int twopower(int64_t n) {
  int64_t p = 1;
  int64_t bit = n;
  bit |= bit>>32;
  bit |= bit>>16;
  bit |= bit>>8;
  bit |= bit>>4;
  bit |= bit>>2;
  bit |= bit>>1;
  bit = (bit+1)>>1;
  while(bit) {
    p *= p * ((bit & n) ? 2 : 1);
    p %= N;
    bit >>= 1;
  }
  return (int)p;
}

int factor(int64_t n, int *p, int *mult, int solvent) {
  int i, j = 0;
  for(i = 0; primes[i]; i++) {
    int mm = 0;
    while(n % primes[i] == 0) {
      mm++;
      n /= primes[i];
    }
    if(mm) {
      p[j] = primes[i];
      mult[j] = mm;
      j++;
    }
    if(n < primes[i] * primes[i]) {
      if (n > 1) {
        p[j] = n;
        mult[j] = 1;
        j++;
      }
      break;
    }
  }
  if(!primes[i]) {
    int g = gcd(n, solvent);
    if (g > 1) {
      int mm = 0;
      while(n % g == 0) {
        mm++;
        n /= g;
      }
      p[j] = g;
      mult[j] = mm;
      j++;
    }
    if (n > 1) {
      p[j] = n;
      mult[j] = 1;
      j++;
    }
  }
  return j;
}

int main() {
  int ncases;
  scanf("%d", &ncases);
  while(ncases--) {
    int kprob, m, n;
    scanf("%d%d%d", &kprob, &m, &n);
    
    int p[P], mmult[P], nmult[P] = {0};
    int nprimes = factor(((int64_t)m)*n, p, mmult, m);
    int n_ = n;
    for(int i=0; i<nprimes; i++)
      while (n_ % p[i] == 0) {
        mmult[i]--;
        nmult[i]++;
        n_ /= p[i];
      }
    
    int k[P] = {0}, l[P] = {0}; // orders
    int64_t sum = 0;
    while(1) {
      int64_t orbits = 1, s;
      int i;
      for(i=0; i<nprimes; i++) {
        int e = mmult[i] + nmult[i] - (k[i] > l[i] ? k[i] : l[i]);
        while(e--)
          orbits *= p[i];
      }
      s = twopower(orbits);
      for(i=0; i<nprimes; i++) {
        for(int j=0; j<k[i]; j++)
          s = (s * (j ? p[i] : p[i]-1)) % N;
        for(int j=0; j<l[i]; j++)
          s = (s * (j ? p[i] : p[i]-1)) % N;
      }
      sum = (sum + s) % N;
      
      k[0]++;
      for(i=0; i < nprimes && k[i] > mmult[i]; k[i]=0, k[++i]++);
      if(i >= nprimes) {
        l[0]++;
        for(i=0; i < nprimes && l[i] > nmult[i]; l[i]=0, l[++i]++);
        if(i >= nprimes) {
          break;
        }
      }
    }

    sum = (sum * modinv(m, N)) % N;
    sum = (sum * modinv(n, N)) % N;

    printf("%d %lld\n", kprob, sum);
  }
  return 0;
}