Description

Daodao对数字比较感兴趣,学了编程之后更是对大数有兴趣.daodao定义了一个函数

int f(int value)

{

　　　　　 Int s=value的所有位数的和;

　　　　　 If(s<=9 ) return s;

　　　　　 Else return f(s);

}

比如value=17就返回8(1+7=8)，value=267就返回6(2+6+7=15,然后递归返回1+5=6)

现在给你一N个数,这些数都是a^b的形式的,daodao想知道这N个数的乘积MulResult在函数f作用下的返回值f(MulResult)

Input

多组数据.每组数据第一行一个N(1<=N<=100),表示有N个数,接下来有N行,每行有两个数a和b(1<=a<=100，0<=b<=10000),表示一个整数a^b.

Output

输出f(MulResult)

Sample

Input

2
2 3
4 2
3
2 2
2 3
2 4

Output

2
8

Hint

Sample 1 : MulResult=2^3 * 4^2 = 128,f(128)=2

Source: zjut_DD