Ants

Computer geeks like trees, and so do ants. We are given a tree with two ants walking along its outer outline — the Left Ant and the Right Ant — exactly as shown in the figure above (they follow the dotted path). Both ants start at the lower end of the trunk, standing on opposite sides of it.

The Left Ant needs 2 seconds to walk along one edge of the tree while moving away from the root (upwards), and 1 second while moving towards the root (downwards). The Right Ant is twice as fast, so it needs 1 second upwards and 0.5 seconds downwards.

Whenever the two ants meet, they both turn around at once and start walking in the opposite directions. If an ant steps off the tree onto the ground, it immediately starts climbing the opposite side of the trunk. The ants are so tiny that they would be invisible even under a microscope (they are drawn larger in the figure only for clarity).

Write a program that computes the exact moment at which the ants turn around for the second time.

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases.

Each test case is described by two lines. The first line contains an even integer $n$ ($2 \le n \le 100\,000\,000$) — the number of edges of the tree. The second line contains a string of $n/2$ characters (digits and lowercase letters a–f) that encodes a $2n$-bit binary number in hexadecimal. This number describes the Left Ant's walk around the whole tree, assuming the Right Ant stays still. Reading the bits from left to right, a bit 1 means the Left Ant walks away from the root along the corresponding edge, and a bit 0 means it walks towards the root. The root has a trunk, i.e. exactly one edge leads out of the root.

The size of the input does not exceed 50 MB, which is far more than the memory available to your program.

Print $t$ lines, one answer per test case. Each answer is the moment (in seconds) at which the ants turn around for the second time, written as an irreducible fraction p/q (with no spaces around /), where $p$ and $q$ are positive integers. If the answer is an integer, then $q = 1$.

Each hexadecimal digit expands to four bits, most significant bit first (for example, f becomes 1111 and b becomes 1011); concatenating them from left to right gives the full $2n$-bit sequence.

Because the walk is a complete tour of the tree, every edge is traversed exactly twice — once away from the root and once towards it — so the sequence always contains exactly $n$ ones and $n$ zeros. The two ants travel the same closed outline in opposite directions.