#include <iostream>
#include <math.h>
using namespace std;
 
int main()
{
    int t;
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
      int rem = 0, n, m, count = 0;
      cin >> n >> m;
 
      for(int q = 0; q < n; q++)
      {
        int nodeatm = pow(2,q) + rem;
        if( nodeatm < m)
        {
            count++;
            rem = 0;
        }
        else
        {
            count += ( nodeatm/ m );
            rem = ( nodeatm % m );
        }
 
      }
 
      if( rem )
         count++;
 
      cout << count << endl;
    }
 
  return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWF0aC5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKaW50IG1haW4oKQp7CiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwogICAgCiAgICBmb3IgKGludCBpID0gMDsgaSA8IHQ7IGkrKykKICAgIHsKICAgICAgaW50IHJlbSA9IDAsIG4sIG0sIGNvdW50ID0gMDsKICAgICAgY2luID4+IG4gPj4gbTsKICAgICAgCiAgICAgIGZvcihpbnQgcSA9IDA7IHEgPCBuOyBxKyspCiAgICAgIHsKICAgICAgICBpbnQgbm9kZWF0bSA9IHBvdygyLHEpICsgcmVtOwogICAgICAgIGlmKCBub2RlYXRtIDwgbSkKICAgICAgICB7CiAgICAgICAgICAgIGNvdW50Kys7CiAgICAgICAgICAgIHJlbSA9IDA7CiAgICAgICAgfQogICAgICAgIGVsc2UKICAgICAgICB7CiAgICAgICAgICAgIGNvdW50ICs9ICggbm9kZWF0bS8gbSApOwogICAgICAgICAgICByZW0gPSAoIG5vZGVhdG0gJSBtICk7CiAgICAgICAgfQogICAgICAgIAogICAgICB9CgogICAgICBpZiggcmVtICkKICAgICAgICAgY291bnQrKzsKICAgICAgICAgCiAgICAgIGNvdXQgPDwgY291bnQgPDwgZW5kbDsKICAgIH0KICAgIAogIHJldHVybiAwOwp9

MwozIDEKMyAyCjEwIDY=

3
3 1
3 2
10 6