Problem: The cool breeze blows gently, the flowing water ripples steadily.

"Flowing and passing like this, the water isn't gone ultimately; Waxing and waning like that, the moon doesn't shrink or grow eventually."

"Everything is transient in a way and perennial in another."

Kanno doesn't seem to make much sense out of Mino's isolated words, but maybe it's time that they enjoy the gentle breeze and the night sky — the inexhaustible gifts from nature.

Gazing into the sky of stars, Kanno indulges in a night's tranquil dreams. 

There is a set S of n points on a coordinate plane.

Kanno starts from a point P that can be chosen on the plane. P is not added to S if it doesn't belong to S. Then the following sequence of operations (altogether called a move) is repeated several times, in the given order:

  1. Choose a line l such that it passes through at least two elements in S and passes through Kanno's current position. If there are multiple such lines, one is chosen equiprobably. 
  2. Move to one of the points that belong to S and lie on l. The destination is chosen equiprobably among all possible ones, including Kanno's current position (if it does belong to S). 



There are q queries each consisting of two integers (t_i, m_i). For each query, you're to help Kanno maximize the probability of the stopping position being the t_i-th element in S after m_i moves with a proper selection of P, and output this maximum probability. Note that according to rule 1, P should belong to at least one line that passes through at least two points from S.

Input

The first line contains a positive integer n (2 ≤ n ≤ 200) — the number of points in S.

The i-th of the following n lines contains two space-separated integers x_i and y_i (-10^4 ≤ x_i, y_i ≤ 10^4) — the coordinates of the i-th point in S. The input guarantees that for all 1 ≤ i < j ≤ n, (x_i, y_i) ≠ (x_j, y_j) holds.

The next line contains a positive integer q (1 ≤ q ≤ 200) — the number of queries.

Each of the following q lines contains two space-separated integers t and m (1 ≤ t_i ≤ n, 1 ≤ m_i ≤ 10^4) — the index of the target point and the number of moves, respectively.

Output

Output q lines each containing a decimal number — the i-th among them denotes the maximum probability of staying on the t_i-th point after m_i steps, with a proper choice of starting position P.

Your answer will be considered correct if each number in your output differs from the corresponding one in jury's answer by at most 10^{-6}.

Formally, let your answer be a, and the jury's answer be b. Your answer is considered correct if |a - b| ≤ 10^{-6}.

Example

Input

5
0 0
1 3
2 2
3 1
4 4
10
1 1
2 1
3 1
4 1
5 1
3 2
3 3
3 4
3 5
3 6


Output

0.50000000000000000000
0.50000000000000000000
0.33333333333333331483
0.50000000000000000000
0.50000000000000000000
0.18518518518518517491
0.15226337448559670862
0.14494741655235482414
0.14332164812274550414
0.14296036624949901017

Note

The points in S and possible candidates for line l are depicted in the following figure.

<image>

For the first query, when P = (-1, -3), l is uniquely determined to be 3x = y, and thus Kanno will move to (0, 0) with a probability of \frac 1 2.

For the third query, when P = (2, 2), l is chosen equiprobably between x + y = 4 and x = y. Kanno will then move to the other four points with a probability of \frac 1 2 ⋅ \frac 1 3 = \frac 1 6 each, or stay at (2, 2) with a probability of \frac 1 3.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3& p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3& p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3& p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3& p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4& p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4& p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4& p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2& p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2& p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2& p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2& p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long Gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return Gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return Gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return {l.first - r.first, l.second - r.second};
}
ostream& operator<<(ostream& os, const vector<long long>& VEC) {
  for (auto v : VEC) os << v << " ";
  return os;
}
ostream& operator<<(ostream& os, const pair<long long, long long>& PAI) {
  os << PAI.first << " : " << PAI.second;
  return os;
}
ostream& operator<<(ostream& os, const pa3& PAI) {
  os << PAI.x << " : " << PAI.y << " : " << PAI.z;
  return os;
}
ostream& operator<<(ostream& os, const pa4& PAI) {
  os << PAI.x << " : " << PAI.y << " : " << PAI.z << " : " << PAI.w;
  return os;
}
ostream& operator<<(ostream& os,
                    const vector<pair<long long, long long> >& VEC) {
  for (auto v : VEC) os << v << " ";
  return os;
}
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long pr[1100000];
long long inv[1100000];
long long comb(long long nn, long long rr) {
  if (rr < 0 || rr > nn || nn < 0) return 0;
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = ((long long)pr[i - 1] * i) % mod;
  }
  inv[ert] = beki(pr[ert], mod - 2, mod);
  for (long long i = ert - 1; i >= 0; i--) {
    inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
  }
}
vector<long long> lin[40100];
vector<long long> G[220];
long long x[220], y[220];
bool on(long long a, long long b, long long c) {
  long long dx1 = x[a] - x[b];
  long long dx2 = x[c] - x[b];
  long long dy1 = y[a] - y[b];
  long long dy2 = y[c] - y[b];
  return dx1 * dy2 == dx2 * dy1;
}
using T = array<array<double, 200>, 200>;
T uni;
const long long sz = 200;
T kake(T A, T B) {
  T ans;
  for (long long i = 0; i < sz; i++)
    for (long long j = 0; j < sz; j++) {
      double ho = 0;
      for (long long k = 0; k < sz; k++) {
        ho += A[i][k] * B[k][j];
      }
      ans[i][j] = ho;
    }
  return ans;
}
T beki(T A, long long r) {
  if (r == 0) return uni;
  if (r == 1) return A;
  if (r % 2)
    return kake(beki(A, r - 1), A);
  else {
    T ho = beki(A, r / 2);
    return kake(ho, ho);
  }
}
T be[16];
using U = array<double, 200>;
U df(long long r, long long t) {
  U hoge;
  for (long long i = 0; i < 200; i++) hoge[i] = 0;
  hoge[t] = 1;
  for (long long ii = 0; ii < 16; ii++)
    if (r & (1 << ii)) {
      U hoge2;
      for (long long i = 0; i < 200; i++) {
        hoge2[i] = 0;
        for (long long j = 0; j < 200; j++) {
          hoge2[i] += be[ii][i][j] * hoge[j];
        }
      }
      swap(hoge2, hoge);
    }
  return hoge;
}
void solve() {
  long long n;
  cin >> n;
  long long cnt = 0;
  for (long long i = 0; i < n; i++) cin >> x[i] >> y[i];
  for (long long i = 0; i < n; i++)
    for (long long j = i + 1; j < n; j++) {
      bool dame = 0;
      for (long long k = 0; k < j; k++)
        if (k != i && k != j) {
          if (on(i, j, k)) dame = 1;
        }
      if (dame) continue;
      lin[cnt].push_back(i);
      lin[cnt].push_back(j);
      for (long long k = j + 1; k < n; k++)
        if (on(i, j, k)) lin[cnt].push_back(k);
      for (auto v : lin[cnt]) G[v].push_back(cnt);
      cnt++;
    }
  T p;
  for (long long i = 0; i < 200; i++)
    for (long long j = 0; j < 200; j++) p[i][j] = 0;
  for (long long i = 0; i < n; i++) {
    long long f = G[i].size();
    for (auto l : G[i]) {
      long long f2 = lin[l].size();
      for (auto v : lin[l]) {
        p[i][v] += 1.0 / (f * f2 + 0.0);
      }
    }
  }
  be[0] = p;
  for (long long i = 1; i < 16; i++) be[i] = kake(be[i - 1], be[i - 1]);
  long long q;
  cin >> q;
  while (q--) {
    long long t, m;
    cin >> t >> m;
    t--;
    U hoge = df(m - 1, t);
    double ans = 0;
    for (long long i = 0; i < cnt; i++) {
      double s = 0;
      long long e = lin[i].size();
      for (auto v : lin[i]) {
        s += hoge[v];
      }
      s /= e;
      ans = max(ans, s);
    }
    printf("%.10lf\n", ans);
  }
}
signed main() {
  mod = 1000000007;
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n = 1;
  for (long long i = 0; i < n; i++) solve();
  return 0;
}