Kick-ass musical offering P22695

Statement

html

It is well known that when Johann Sebastian Bach visited Frederick II of Prussia in his residence in Potsdam on May 7, 1747, the king was particularly boastful of his collection of the recently invented fortepianos. It is also known that he gave the composer a small theme of his own creation, challenging him to improvise a three-voice fugue. History books record how the master politely replied that he needed to work on the score and, two months later, published a set of pieces based on the theme, with the inscription Regis Iussu Cantio Et Reliqua Canonica Arte Resoluta—which we know today as The Musical Offering.

However, some recent studies suggest that the historians at the service of the king reported a slightly distorted version of the events. What the new evidence suggests is that, actually, the musician replied to the king’s challenge with a “Game on!”, and they engaged in a fortepiano duel where each one was improvising to the best of their skills—and where, as expected, Bach kicked Frederick’s royal ass. To those watching the event, the clash must have been a remarkable cacophony. However, the two contenders would occasionally play the same note simultaneously, and a brief moment of acoustical relief would happen.

Given the two scores of the master and the king, which they were looping endlessly, can you tell what fraction of the time the two players were in unison?

Input

Input begins with the number of cases n. Follow n pairs of scores. Every score begins with the number of notes 1 ≤ m ≤ 100, followed by m pairs (note, length). The notes are lowercase letters between ‘a’ and ‘g’. The lengths are powers of two between 1 and 64, where ℓ means that the note was played for 1/ℓ of a second.

Output

For every case, print the simplified fraction of the time that the two players were striking the same note. A denominator of “/1” must be omitted.

Public test cases

Input

6
1 a 1      1 b 1
1 a 8      1 a 4
2 a 8 b 4  2 a 4 b 8
2 a 4 b 4  3 a 4 b 4 a 4
1 a 32     2 a 32 b 64
1 a 1      2 a 1 b 2

Output

0
1
2/3
1/2
2/3
2/3

Information

Author: Edgar Gonzàlez
Language: English
Official solutions: C++
User solutions: C++