Problem: Cold winter evenings in Tomsk are very boring — nobody wants be on the streets at such a time. Residents of Tomsk while away the time sitting in warm apartments, inventing a lot of different games. One of such games is 'Colored Jenga'.

This game requires wooden blocks of three colors: red, green and blue. A tower of n levels is made from them. Each level consists of three wooden blocks. The blocks in each level can be of arbitrary colors, but they are always located close and parallel to each other. An example of such a tower is shown in the figure.

<image>

The game is played by exactly one person. Every minute a player throws a special dice which has six sides. Two sides of the dice are green, two are blue, one is red and one is black. The dice shows each side equiprobably.

If the dice shows red, green or blue, the player must take any block of this color out of the tower at this minute so that the tower doesn't fall. If this is not possible, the player waits until the end of the minute, without touching the tower. He also has to wait until the end of the minute without touching the tower if the dice shows the black side. It is not allowed to take blocks from the top level of the tower (whether it is completed or not).

Once a player got a block out, he must put it on the top of the tower so as to form a new level or finish the upper level consisting of previously placed blocks. The newly constructed levels should have all the same properties as the initial levels. If the upper level is not completed, starting the new level is prohibited.

For the tower not to fall, in each of the levels except for the top, there should be at least one block. Moreover, if at some of these levels there is exactly one block left and this block is not the middle block, the tower falls.

The game ends at the moment when there is no block in the tower that you can take out so that the tower doesn't fall.

Here is a wonderful game invented by the residents of the city of Tomsk. I wonder for how many minutes can the game last if the player acts optimally well? If a player acts optimally well, then at any moment he tries to choose the block he takes out so as to minimize the expected number of the game duration.

Your task is to write a program that determines the expected number of the desired amount of minutes.

Input

The first line of the input contains the only integer n (2 ≤ n ≤ 6) — the number of levels in the tower.

Then n lines follow, describing the levels of the tower from the bottom to the top (the first line is the top of the tower). Each level is described by three characters, the first and the third of them set the border blocks of the level and the second one is the middle block. The character that describes the block has one of the following values 'R' (a red block), 'G' (a green block) and 'B' (a blue block).

Output

In the only line of the output print the sought mathematical expectation value. The answer will be considered correct if its relative or absolute error doesn't exceed 10 - 6.

Examples

Input

6
RGB
GRG
BBB
GGR
BRG
BRB


Output

17.119213696601992

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
inline unsigned long long getint() {
  unsigned long long _x = 0, _tmp = 1;
  char _tc = getchar();
  while ((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar();
  if (_tc == '-') _tc = getchar(), _tmp = -1;
  while (_tc >= '0' && _tc <= '9') _x *= 10, _x += (_tc - '0'), _tc = getchar();
  return _x * _tmp;
}
inline unsigned long long add(unsigned long long _x, unsigned long long _y,
                              unsigned long long _mod = 1000000007ll) {
  unsigned long long _ = _x + _y;
  if (_ >= _mod) _ -= _mod;
  return _;
}
inline unsigned long long sub(unsigned long long _x, unsigned long long _y,
                              unsigned long long _mod = 1000000007ll) {
  unsigned long long _ = _x - _y;
  if (_ < 0) _ += _mod;
  return _;
}
inline unsigned long long mul(unsigned long long _x, unsigned long long _y,
                              unsigned long long _mod = 1000000007ll) {
  unsigned long long _ = _x * _y;
  if (_ >= _mod) _ %= _mod;
  return _;
}
unsigned long long mypow(unsigned long long _a, unsigned long long _x,
                         unsigned long long _mod) {
  if (_x == 0) return 1ll;
  unsigned long long _tmp = mypow(_a, _x / 2, _mod);
  _tmp = mul(_tmp, _tmp, _mod);
  if (_x & 1) _tmp = mul(_tmp, _a, _mod);
  return _tmp;
}
unsigned long long mymul(unsigned long long _a, unsigned long long _x,
                         unsigned long long _mod) {
  if (_x == 0) return 0ll;
  unsigned long long _tmp = mymul(_a, _x / 2, _mod);
  _tmp = add(_tmp, _tmp, _mod);
  if (_x & 1) _tmp = add(_tmp, _a, _mod);
  return _tmp;
}
inline bool equal(double _x, double _y) {
  return _x > _y - 1e-9 && _x < _y + 1e-9;
}
int __ = 1, _cs;
void build() {}
int n;
char c[6][6];
inline int chg(char ctmp) {
  if (ctmp == 'R') return 1;
  if (ctmp == 'G') return 2;
  if (ctmp == 'B') return 3;
  return 0;
}
int er[3] = {60, 51, 15};
int s[1021];
void init() {
  n = getint();
  for (int i = 0; i < n; i++) scanf("%s", c[i]);
}
int vv[1021];
inline unsigned long long hsh(int lst) {
  for (int i = 0; i <= lst; i++) {
    int i1 = s[i] & 3;
    int i2 = (s[i] >> 2) & 3;
    int i3 = (s[i] >> 4) & 3;
    if (i1 > i3) swap(i1, i3);
    vv[i] = (i1 << 4) + (i2 << 2) + i3;
  }
  sort(vv, vv + lst);
  unsigned long long thsh = 0;
  for (int i = 0; i <= lst; i++) thsh = thsh * 5147 + vv[i];
  return thsh;
  return thsh * 5147 + lst;
}
const int P = 10215001;
struct Hash {
  int from[P], nxt[P], stmp;
  unsigned long long vl[P];
  double res[P];
  Hash() { stmp = 0; }
  double value(unsigned long long x) {
    for (int i = from[x % P]; i; i = nxt[i])
      if (vl[i] == x) return res[i];
    return -1;
  }
  void add(unsigned long long x, double r) {
    if (value(x) > -0.5) return;
    vl[++stmp] = x;
    res[stmp] = r;
    nxt[stmp] = from[x % P];
    from[x % P] = stmp;
  }
} dp;
const double pr[4] = {1. / 6., 1. / 6., 2. / 6., 2. / 6.};
double DP(int lst) {
  unsigned long long hsvl = hsh(lst);
  double tvl = dp.value(hsvl);
  if (tvl > -0.5) return tvl;
  double bst[4];
  for (int i = 0; i < 4; i++) bst[i] = 1e9;
  int xc[3] = {}, nxt = lst;
  for (int i = 0; i < 3; i++) xc[i] = (s[nxt] >> (i << 1)) & 3;
  if (xc[0] > 0 && xc[1] > 0 && xc[2] > 0) {
    nxt++;
    xc[0] = xc[1] = xc[2] = 0;
  }
  for (int i = 0; i < lst; i++) {
    int wc[3] = {}, sum = 0;
    for (int j = 0; j < 3; j++) {
      wc[j] = (s[i] >> (j << 1)) & 3;
      if (wc[j] > 0) sum++;
    }
    if (sum <= 1) continue;
    for (int j = 0; j < 3; j++) {
      int tc = wc[j];
      if (tc == 0) continue;
      if (sum == 2 && (j == 1 || !wc[1])) continue;
      int si = s[i];
      s[i] &= er[j];
      wc[j] = 0;
      if (sum == 2 || !wc[1]) s[i] = 0;
      for (int k = 0; k < 3; k++)
        if (xc[k] == 0) {
          s[nxt] |= tc << (k << 1);
          bst[tc] = min(bst[tc], DP(nxt));
          s[nxt] &= er[k];
        }
      s[i] = si;
      wc[j] = tc;
    }
  }
  double ans = 1.0, kp = pr[0];
  for (int i = 1; i <= 3; i++)
    if (bst[i] < 1e9)
      ans += bst[i] * pr[i];
    else
      kp += pr[i];
  if (kp > .99)
    ans = 0.0;
  else
    ans /= (1. - kp);
  dp.add(hsvl, ans);
  return ans;
}
void solve() {
  for (int i = 0; i < n; i++) {
    int c1 = chg(c[i][0]);
    int c2 = chg(c[i][1]);
    int c3 = chg(c[i][2]);
    if (c1 > c3) swap(c1, c3);
    s[i] = (c3 << 4) + (c2 << 2) + c1;
  }
  printf("%.12f\n", DP(n - 1));
}
int main() {
  build();
  while (__--) {
    init();
    solve();
  }
}