#P3445. Elementary Additions

Elementary Additions

题目描述

在当今环境下,学生们过于依赖计算器和计算机来进行简单的算术运算。可悲的是,大学生们如果没有电子设备的辅助就无法进行简单算术运算的情况并不少见。Peano教授受够了。他决定亲自出手,强迫学生们熟练掌握最基本的算术技能:非负整数的加法。由于学生们在这方面基础薄弱,他决定回归基础,用集合论来表示非负整数。

非负整数的表示方法如下:

  • 0 用空集 {} 表示。
  • 对于任何大于 0 的数字 nn 用一个包含所有小于 n 的非负整数的集合表示。

例如,前 4 个非负整数的表示如下:

0 => {}
1 => {{}}
2 => {{}, {{}}}
3 => {{}, {{}}, {{}, {{}}}}

以此类推。注意,集合的基数(大小)正好等于它所表示的整数。尽管集合的元素通常是无序的,但Peano教授要求集合的元素按基数递增的顺序排列,以便更容易评分。此外,Peano教授确信没有任何计算器或计算机程序能够处理这种表示法下的数字运算。

不出所料,许多学生无法应对这一基本任务,如果他们不能很快得到帮助,就会挂科。现在,作为一名有进取心的计算机科学学生,你需要帮助他们。你决定编写一个名为“公理作弊机”(ACM)的计算机程序,卖给学生们,帮助他们完成加法运算以通过课程。

输入格式

输入的第一行是一个正整数,表示测试用例的数量。每个测试用例有两行输入,每行包含一个用集合表示法表示的非负整数。每行仅包含字符 {},。给定的两个整数的和最多为 15。

输出格式

对于每个测试用例,输出两个输入整数的和,用上述集合表示法表示。

示例输入 1

3
{}
{}
{{}}
{{},{{}}}
{{},{{}},{{},{{}}}}
{{}}

示例输出 1

{}
{{},{{}},{{},{{}}}}
{{},{{}},{{},{{}}},{{},{{}},{{},{{}}}}}

来源

Rocky Mountain 2007