1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <vector>
#include <cstdio>
#include <cstdlib>
#include "dzilib.h"

#define FORD(a,b,c) for (int a = (b); a>=(c); --a)

using namespace std;

typedef long long LL;

#define DEBUG(x)
#define DEB2(x)

LL N;
bool m34, m25, m49, m45, m39;

int pyt(LL y) {
  vector<int> pot;
  int res = Ask(y);
  m25 = (res%25==0);
  m34 = (res%34==0);
  m39 = (res%39==0);
  m45 = (res%45==0);
  m49 = (res%49==0);
//  fprintf(stderr, "-> %d\n", res);
/*  FORD(x, 36, 32)
    if (res%x==0)
      return x;
  FORD(x, 28, 24)
    if (res%x==0)
      return x;*/
  int p = 2;
  pot.clear();
  while (res>1) {
    if (res%p==0) {
      res /= p;
      pot.push_back(p);
    }
    else
      p++;
  }
  DEBUG(
  for (int x : pot)
    fprintf(stderr, "%d ", x);
  fprintf(stderr, "    %s\n", m34 ? "?34" : "");
  )
  return pot.back();
}

bool czy_pierwsza(int x) {
  for(int a = 2; a*a<=x; a++)
    if (x%a==0)
      return 0;
  return 1;
}

long long share_hidden_x = 0;

void solve() {
  #define START 3
  LL przes = 10+rand()%1000, przes1;
  int mam = 0, ile_kr = 0, zle = 2000;
  for (;;) {
    DEBUG(fprintf(stderr, "%lld\n", share_hidden_x+przes);)
    int teraz = pyt(przes); ++ile_kr;
    if (mam==31 && m34) teraz = 34;
    if (mam==23 && m25) teraz = 25;
    if (mam==37 && m39) teraz = 39;
    if (mam==47 && m49) teraz = 49;
    if (mam==43 && m45) teraz = 45;
    if (teraz-1>max(START-2, mam)) {
      if (mam==0) przes1 = przes;
      przes += (1LL<<(teraz-1));
      mam = teraz;
      DEBUG(fprintf(stderr, "OK %d %lld %lld\n", mam, share_hidden_x+przes, (1LL<<mam));)
      DEB2(fprintf(stderr, "%d po %d\n", mam, ile_kr);)
      if (N+przes<2*(1LL<<mam)) {
        DEB2(fprintf(stderr, "ODPOWIEDZ: %lld\n", (1LL<<mam)-przes);)
        Answer((1LL<<mam)-przes);
        return;
      }
      // ide co 2^mam, chce dojsc do 2^{p-1}
      int p2 = mam+1;
      while (!czy_pierwsza(p2))
        p2++;
      zle = 2*(1LL<<(p2-1-mam));
      DEBUG(fprintf(stderr, "limit: %d -> %d\n", p2, zle);)
      ile_kr = 0;
    }
    else
    if (ile_kr>=zle) {
      DEB2(fprintf(stderr, "ZA DLUGO - WRACAM po %d\n", ile_kr);)
      mam = 0;
      ile_kr = 0;
      zle = 2000;
      przes += (przes1 + (1<<(START-1)) - przes%(1<<(START-1))) % (1<<(START-1));
    }
    else
      przes += (1LL<<mam);
  }
}

int main() {
  int t = GetT();
  //int q = GetQ();
  //long long c = GetC();
  N = GetN();
  while (t--) {
    solve();
/*    if (Ask(1) == 8) Answer(1000);
    else Answer(1);*/
  }
  return 0;
}