Background

Special for beginners, ^_^

Description

给你N个数对(Ai,Bi)，令M=A1^B1 * A2^B2 * … * AN^BN。现在，你要写一个程序，求出最小的整数X，满足X! mod M=0。

Format

Input

第一行一个正整数test，表示有test组数据。对于每组数据，第一行一个正整数N，接下来N行，每行两个正整数Ai和Bi。

Output

共test行，为对于每组的答案。

Samples

2
2 
3 2
4 1
1 
1 10000000000000

6
0

Limitation

对于100%的数据，1<=test<=50，1<=N<=100，1<=Ai<=100，1<=Bi<=10^13；