public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		TheLoversUnSolved sol = new TheLoversUnSolved();
		int T = sc.nextInt();
		double[] N = new double[T];
		double[] K = new double[T];
		for (int i = 0; i < T; i++) {
			N[i] = sc.nextDouble();
			K[i] = sc.nextDouble();
		}
		for (int i = 0; i < T; i++) {
//			sol.memo = new double[N[i] + 1][K[i] + 1];
			sol.d = new HashMap<Double, HashMap<Double, Double>>();
			double val = sol.calcRec(N[i], K[i]);
			System.out.println((int)val);
		}
	}