Employee Bonus Calculation

Given a hierarchy of employees, each with a performance score and an optional manager, you are to compute the final bonus for every employee. The base bonus for an employee is computed as 100 times their performance score. In addition, if an employee has a manager, the manager's bonus is added to their own bonus. This dependency is recursive, meaning that if a manager in turn has a manager, that bonus will also be added, and so on.

The formula for the bonus of an employee i can be expressed in LaTeX as:

\(Bonus_i = 100 \times score_i + \begin{cases} Bonus_{manager_i} & \text{if } manager_i \neq \text{None} \\ 0 & \text{otherwise} \end{cases}\)

After computing the bonuses, output the bonus for each employee sorted in lexicographical (alphabetical) order of employee identifiers. The input consists of one or more test cases.

inputFormat

The input is read from standard input. The first line contains an integer T, representing the number of test cases. For each test case, the first line contains an integer N, the number of employees. This is followed by N lines, each containing three items separated by spaces:

• employee_id: a string representing the employee's identifier. • performance_score: an integer representing the employee's performance score. • manager_id: a string representing the manager's identifier or "None" if the employee has no manager.

outputFormat

For each test case, output the final bonus of each employee on separate lines in the format 'employee_id bonus', sorted in lexicographical order by employee_id. Separate the outputs of consecutive test cases with a blank line.## sample

2
4
alice 10 None
bob 8 alice
carol 15 bob
dave 5 alice
3
eve 7 None
frank 9 eve
grace 6 frank

alice 1000
bob 1800
carol 3300
dave 1500
eve 700
frank 1600
grace 2200