#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define getchar getchar_unlocked #define putchar putchar_unlocked using namespace std; typedef long long int64; typedef long long unsigned uint64; typedef long double float80; typedef unsigned short uint16; typedef unsigned uint; typedef unsigned char uint8; const uint N_PRIMES = 14; const uint STATE_MAX = 1 << N_PRIMES; const uint BITS = 65; typedef double prob_t; uint64 primes[N_PRIMES]; uint phi_two[STATE_MAX]; uint state_min_two[STATE_MAX]; prob_t probs_cumu[STATE_MAX][BITS]; prob_t probs_cumucumu[STATE_MAX][N_PRIMES][BITS]; prob_t probs_same[STATE_MAX]; prob_t probs_pos[STATE_MAX]; prob_t probs_neg[STATE_MAX]; prob_t state_prods[STATE_MAX]; prob_t state_phis[STATE_MAX]; prob_t pows[BITS]; prob_t dp[STATE_MAX]; inline uint ilog2(uint64 x) { union { uint64 u64; double d; } n; n.d = double(x) + 0.5; return (n.u64 >> 52) - 1023; } void init(uint N) { // O(2^N * N * log(max{E_i})) const uint state_max = 1 << N; pows[0] = 1.0; for (uint i = 1; i < BITS; ++i) { pows[i] = pows[i-1] * 0.5; } uint max_two = 0; for (uint i = 0; i < N; ++i) { uint64 phi = primes[i] - 1; phi_two[i] = ilog2(phi & -phi); max_two = max(max_two, phi_two[i]); } for (uint i = 0; i < state_max; ++i) { for (uint j = 0; j <= max_two; ++j) { probs_cumu[i][j] = 1.0; } probs_same[i] = 1.0; probs_pos[i] = 1.0; probs_neg[i] = 1.0; state_prods[i] = 1.0; state_phis[i] = 1.0; state_min_two[i] = 1e9; } for (uint state = 1; state < state_max; ++state) { uint f = state & -state; uint pstate = state ^ f; uint idx = ilog2(f); uint two = phi_two[idx]; state_min_two[state] = min(state_min_two[pstate], two); prob_t p = primes[idx]; probs_pos[state] = probs_pos[pstate] / p; probs_neg[state] = probs_neg[pstate] * (1. - 1. / p); state_prods[state] = state_prods[pstate] * p; state_phis[state] = state_phis[pstate] * (p - 1.0); prob_t pw = pows[two]; prob_t q = pw; probs_same[state] = probs_same[pstate] * pw; for (uint i = 0; i <= two; ++i) { probs_cumu[state][i] = probs_cumu[pstate][i] * q; if (i > 0) { pw *= 2.0; } q += pw; } for (uint i = two + 1; i <= max_two; ++i) { probs_cumu[state][i] = probs_cumu[pstate][i]; } // x_0 y_1 + x_1 y_2 + ... for (uint t = 1; t < N; ++t) { pw = 1.0; probs_cumucumu[state][t][1] = probs_cumu[state][0]; for (uint i = 2; i <= max_two; ++i) { pw /= pows[t]; probs_cumucumu[state][t][i] = probs_cumucumu[state][t][i-1] + probs_cumu[state][i-1] * pw; } } } } inline uint pop_count(uint n) { return __builtin_popcount(n); } prob_t calc(const uint N) { // O(3^N) const uint total = 1 << N; for (uint state = 1; state < total; ++state) { if ( (state & (state - 1)) == 0) { dp[state] = 1.0; continue; } prob_t Q = state_phis[state]; prob_t P = state_prods[state]; prob_t expected_count = 1.0; prob_t prob_not_repeat = 0.0; for (uint left_state = (state - 1) & state; left_state > 0; left_state = (left_state - 1) & state) { uint right_state = state ^ left_state; prob_t p1 = probs_pos[left_state] * probs_neg[right_state]; prob_t p2 = probs_same[right_state] * probs_cumucumu[left_state][pop_count(right_state)][state_min_two[right_state]] * Q / P; prob_t p3 = p1 + p2; expected_count += p3 * (dp[left_state] + dp[right_state]); prob_not_repeat += p3; } expected_count /= prob_not_repeat; dp[state] = expected_count; } return dp[total - 1]; } void solve() { uint T; assert(1 == scanf("%u", &T)); assert(1 <= T && T <= 1000); for (; T; --T) { uint N; assert(1 == scanf("%u", &N)); assert(1 <= N && N <= N_PRIMES); for (uint i = 0; i < N; ++i) { assert(1 == scanf("%llu", &primes[i])); assert(3 <= primes[i] && primes[i] < (1ull << 63)); } init(N); prob_t ans = calc(N); printf("%.8lf\n", ans); } } int main() { solve(); return 0; }