#below is my code for the tilling problem, kindly tell me the solution in java only because in editorial also solution is provided in cpp#
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
int m = sc.nextInt();
System.out.println(countWay(n, m));
}
}
public static int countWay(int n, int m) {
int count[] = new int[n + 1];
count[0] = 0;
for (int i = 1; i <= n; i++) {
if (i > m) {
count[i] = count[i - 1] + count[i - m];
} else if (i < m || i == 1) {
count[i] = 1;
} else {
count[i] = 2;
}
}
return count[n];
}
}