• Source 
    1. #include <iostream>
    2. using namespace std;
    3.  
    4. int countTiles(int n,int m){
    5.     //Base case
    6.     if(n>=1 && n<m)
    7.     return 1;
    8.     if(n==m)
    9.     return 2;
    10.     //recursive case
    11.     else return(countTiles(n-1,m)+countTiles(n-m,m));
    12. }
    13.  
    14. int main() {
    15. 	// your code goes here
    16. 	int t,n,m;
    17. 	cin>>t;
    18. 	while(t--) {
    19. 	    cin>>n>>m;
    20. 	    cout<<countTiles(n,m)<<endl;
    21. 	}
    22. 	return 0;
    23. }