小明和小天在玩牌。有两堆牌，每堆有 n 张，每张牌有一个分值。两人轮流从任何一堆牌中拿走最上面或最下面那张牌，牌上的分数即为其该次得分，最终分数为各次得分之和。两人都足够聪明，目的都是取得最终最大得分。 假设小明第一个拿牌。请编程求出，小明最终能得到多少分。 输入 第一行一个整数 t（1≤t≤10），表示数据组数。接下来每组数据： 第一行一个整数 n（1≤n≤20）； 第二行 n 个整数 ai（1≤ai≤104），表示第一堆牌从上到下每张牌的分数； 第三行 n 个整数 bi（1≤bi≤104），表示第二堆牌从上到下每张牌的分数。 输出 每组数据输出一行一个整数，表示相应答案。 样例输入

2 1 23 53 3 10 100 20 2 4 3

样例输出

53 105