题目内容

仓库要发出 $m$ 只标准货箱。第 $i$ 只货箱里目前已有 $p_i$ 个零件和 $q_i$ 个垫片，数量彼此可能不同。

为使每只货箱最终拥有相同的零件数、相同的垫片数（零件数与垫片数不必相等），工人每次可以做且仅做下面三种操作之一，每种操作计为 $1$ 次取货：

1. 取 $1$ 个零件，放入任意一只货箱；
2. 取 $1$ 个垫片，放入任意一只货箱；
3. 同时取 $1$ 个零件与 $1$ 个垫片，且必须放进同一只货箱。

请计算：最少需要多少次取货，才能把全部货箱配齐。

输入描述

第一行一个正整数 $g$（$1\le g\le 100$），表示询问组数。

接下来共有 $g$ 组数据，每一组格式如下：

第一行一个正整数 $m$（$1\le m\le 1000$），表示货箱个数。

此后 $m$ 行，第 $i$ 行两个正整数 $p_i,q_i$（$1\le p_i,q_i\le 1000$），表示第 $i$ 只货箱当前的零件数与垫片数。

输出描述

输出一行，包含 $g$ 个整数，相邻整数之间用单个空格隔开。

第 $t$ 个数表示第 $t$ 组询问的最少取货次数。

样例1

输入

2
1
5 3
3
1 4
3 1
2 2

输出

0 7

说明

第一组：只有一只货箱，无需补齐，答案为 $0$。

第二组：最终需把零件都补到 $3$、垫片都补到 $4$。三只货箱分别还需 $(2,0)$、$(0,3)$、$(1,2)$，最少取货次数为 $2+3+2=7$。