欢迎加入西电微软俱乐部招新群 588166170,做出福利题,免技术部第一次面试且赠送“福利”海报或小礼品~~~~

问题 1041. -- Franky的游戏O

1041: Franky的游戏O

时间限制: 1 Sec  内存限制: 128 MB
提交: 94  解决: 48
[提交][状态][讨论版]

题目描述

Frankysuper的人造人,来到了n*m的棋盘世界玩冒险游戏。

n×m的棋盘由n行每行m个方格组成,左上角的方格坐标是(0,0),右下角的方格坐标是(n-1,m-1)

每次游戏时,他可以降落在棋盘的任意点,并以此为起点开始周游棋盘世界,他的移动规则是:

只能朝向左上(-1,-1),右上(-1,1),左下(1,-1),右下移动(1,1)四个向量移动。

不过这个棋盘世界很特殊:

它的边界是联通的,例如,在7×9的棋盘中 能从(0,0)移动到(6 ,8)

(1,0)移动到(0,8)(2,8) ...等等。

更精确地说当他从(x,y)以向量(Vx,Vy)移动后,他的坐标是( (x+Vx)%n , (y+Vy)%m );

现在Franky想知道,他最少要玩几次游戏才能遍历完整个棋盘世界。

PS:猜一猜,有公式喔!

PS2:只和奇偶性有关喔,推推小数据看。

输入

有多组输入数据。

输入数据的第一行为一个数字T,代表有T组输入数据 (0<T1000)

接下来为T组测试数据。每组数据占一行,为2个整数n,m(1n,m10000)

输出

对于每一组数据,在1行上输出一个整数, 表示Franky最少要玩的游戏次数。

样例输入

2
2 2
2 3

样例输出

2
1

提示

来源

[提交][状态][讨论版]