// Arup Guha
// 10/16/2016
// Solution to 2015 NY Regional Problem E: A Rational Sequence

import java.util.*;

public class e {

	public static void main(String[] args) {

		Scanner stdin = new Scanner(System.in);
		int numCases = stdin.nextInt();

		// Process each case.
		for (int loop = 0; loop<numCases; loop++) {

			// Get case.
			int caseNum = stdin.nextInt();
			StringTokenizer tok = new StringTokenizer(stdin.next(),"/");
			long num = Long.parseLong(tok.nextToken());
			long den = Long.parseLong(tok.nextToken());
			String p = path(num, den, "");
			
			// This is the wrapper recursive call to solve the problem.
			System.out.println(caseNum+" "+rank(p));
		}
	}

	// Builds the path backwards via recursion. cur is what we've traveled so far, the
	// curNum/curDen is the fraction in our current node as we go up the tree.
	// If we're at the root, we return the Ls and Rs that correspond to the path back to the original node.
	public static String path(long curNum, long curDen, String cur) {

		if (curNum == 1 && curDen == 1) return cur;

		if (curNum > curDen) return path(curNum-curDen, curDen, "1"+cur);
		return path(curNum, curDen-curNum, "0"+cur);

	}

	// Returns the rank of the node specified by path.
	public static long rank(String path) {

		long res = 1L;
		for (int i=0; i<path.length(); i++) {
			if (path.charAt(i) == '0')
				res *= 2;
			else
				res = 2*res+1;
		}
		return res;
	}
}