时间限制：1s

空间限制：256MB

题目描述

数数

有$T$组询问，每组询问给定一个数$n$，求最小的数$x$满足$x!$是$n$的倍数。

众所周知，任意正整数可以表示为若干质数的乘积，即$n=\prod_{i=1}^{t} p_i^{k_i}$，其中$m$是$n$的质因数个数，$p_i$就是第$i$个质因数，$k_i$就是第$i$个质因数的次数。

由于$n$很大，我们将告诉你$t,p_i$和$k_i$。

输入格式

第一行包含$1$个整数 $T$ 。

接下来$T$行，每行第一个整数$t$，然后是$2 \times t$个整数$p_1, k_1, p_2, k_2 ... p_t, k_t$ 。

输出格式

$T$行，每行一个整数。

样例

样例输入

5
1 17 1
1 2 2
2 2 2 5 1
1 11 1
2 2 1 5 1

样例输出

17
4
5
11
5

样例解释

$n_1 = 17, n_2=4, n_3=20, n_4 =11, n_5=10$

数据范围

$20\%$的数据满足$1\le T \le 10$, $1 \le n=\prod_{i=1}^{t} p_i^{k_i} \le 20$

$60\%$的数据满足$1\le T \le 10$, $1 \le t \le 10$, $1 \le p_i \le 10^2且为质数$, $1 \le k_i \le 10^2$

$100\%$的数据满足$1\le T \le 10^3$, $1 \le t \le 50$, $1 \le p_i \le 10^4且为质数$, $1 \le k_i \le 10^4$