题目描述

现在有一个非常大的整数 $x$，可以将其表示为$x = \prod_{i = 1}^{n} p_{i}^{c_{i}}$，$p_{i}$代表一个质数，请问有多少对 $x$的因子是互质的。

输入描述

第一行输入一个整数 $T$$(1 \leq T \leq 10^{2})$，代表有 $T$组测试样例。 对于每一个测试样例第一行的输入一个整数n$(1 \leq n \leq 10^{4})$。 接下来 $n$行，每行两个整数分别代表 $p_{i}$和 $c_{i}$，其中 $1 \leq p_{i}, c_{i} \leq 10^9$，保证$p_{i}$是一个质数，且互不相同。

输出描述

输出 $T$行，每行一个整数代表答案，答案可能会很大，请对 $10^{9} + 7$取模。

样例输入

1
2
2 2
3 1

样例输出

15

样例解释

x = 12，因子为1,2,3,4,6,12

互质的因子对为

(1, 1), (1, 2), (1, 3), (1, 4), (1, 6)

(1, 12), (2, 1), (2, 3), (3, 1), (3, 2)

(3, 4), (4, 1), (4, 3), (6, 1), (12, 1)共15对