2749 - [HAOI2012]外星人

Input

Output

输出test行，每行一个整数，表示答案。

Examples

Input

1
2
2 2
3 1

Output

3

Hint

Test<=50 Pi<=10^5,1<=Q1<=10^9

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题