Description

Format

Input

第一行，输入一个数 q，表示 q 次询问。 接下来 q 行，每行输入两个数 x,y，表示查询的两个点。

Output

对于每组询问，记最长路为 l，你需要输出 e^l。可以证明 e^l 一定是正整数。

Samples

9 
1 2 
1 3 
5 97 
9 114514 
133 13131 
233 22222 
114514 1919810 
1919810 998244353 
19260817 20050110

1 
1 
4 
207 
12
12 
4 
34 
1

Limitation

1s, 1024KiB for each test case.