I. 晶体融合
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

猪猪学院的魔法师小猪们正在制作一把强大的元素法杖。

为了制作这把法杖，他们准备了许多魔法晶体。每块魔法晶体都有一个元素强度，且元素强度均为正整数。

这些魔法晶体共有 $$$k$$$ 种不同的元素强度。其中，元素强度为 $$$v_i$$$ 的魔法晶体有 $$$c_i$$$ 块。

魔法师小猪们需要不断融合魔法晶体，直到最后只剩下一块魔法晶体。

每次融合时，可以选择两块当前存在的魔法晶体。若它们的元素强度分别为 $$$x,y$$$，那么融合后会得到一块元素强度为 $$$x+y$$$ 的新的魔法晶体，同时消耗数量为 $$$f(x, y)$$$ 的魔力值。

这里 $$$f(x, y)$$$ 表示最大的满足 $$$3^e$$$ 能够整除$$$^{\text{∗}}$$$ $$$\dbinom{x+y}{x}$$$$$$^{\text{†}}$$$ 的非负整数 $$$e$$$。即：

$$$$$$ f(x, y) = \max\left\{ e\in\mathbb Z_{\ge 0} : 3^e\mid \dbinom{x+y}{x} \right\} $$$$$$

最终，所有魔法晶体都会被融合成唯一一块魔法晶体，并镶嵌到元素法杖上。

容易发现，最后得到的魔法晶体的元素强度总是所有初始魔法晶体的元素强度之和。因此，无论魔法师小猪们如何安排融合顺序，最终这块魔法晶体的元素强度都是确定的。

小猪们想知道，如果合理安排融合顺序，将所有魔法晶体融合成一块，总计至少需要消耗多少魔力值。

给定所有初始魔法晶体的信息，请你求出这个最小总魔力值。

$$$^{\text{∗}}$$$对于整数 $$$a$$$ 和 $$$b$$$，如果 $$$a$$$ 是 $$$b$$$ 的倍数，即存在一个整数 $$$k$$$，使得 $$$a = k b$$$，则我们称 $$$b$$$ 能整除 $$$a$$$，记作 $$$b \mid a$$$。

$$$^{\text{†}}$$$对于整数 $$$0\le b\le a$$$，$$$\dbinom{a}{b}$$$ 表示从 $$$a$$$ 个不同元素中选出 $$$b$$$ 个元素的方案数。

Input

本题的输入包含多组测试用例。

第一行一个整数 $$$T$$$（$$$1 \leq T \leq 100$$$），表示测试用例的数量。对于每组测试用例：

  • 第一行一个整数 $$$k$$$（$$$1\le k\le 10^5$$$），表示不同元素强度的种数。
  • 接下来 $$$k$$$ 行，每行包含两个整数 $$$v_i,c_i$$$（$$$1\le v_i,c_i\le 10^{18}$$$），表示元素强度为 $$$v_i$$$ 的魔法晶体有 $$$c_i$$$ 块。
  • 数据保证 $$$\sum_{i=1}^{k} v_i c_i \le 10^{18}$$$，并且 $$$v_1,v_2,\ldots,v_k$$$ 两两不同。

保证所有测试用例的 $$$k$$$ 的总和不超过 $$$10^5$$$。

Output

对于每组测试用例：输出一行一个整数，表示所需的最小总魔力值。

可以证明，在本题数据范围内，答案可以用 64 位有符号整数存储。

Example
Input
4
2
1 2
2 1
2
2 1
7 1
1
10 1
1
1 10
Output
1
2
0
4