题目描述

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

众所周知，任意正整数可以表示为若干质数的乘积，即$n=\prod^t_{i=1}p^{k_i}_ 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

数据范围

$100\%$的数据满足$1\le T\le10^3$，$1\le t\le50$，$1\le p_i\le10^4且为质数$，$1\le k_i\le10^4$