有一个国家，这里有一个国王，这一天国王过生日，下面的大臣给国王买了一个 \(n \times m\) 的蛋糕，现在这些大臣准备分蛋糕，由于国王非常喜欢正方形，大臣们为了让国王开心，每一次切蛋糕的时候都会切当前尺寸蛋糕能满足的最大的正方形部分，例如 $4 \times 6$的蛋糕，第一次肯定切 $1$ 个 $4 \times 4$ 的，然后剩下 $2 \times 4$ ，第二次切 $2 \times 2$ 的，依次类推。现在大臣们想知道在所有蛋糕均为正方形的时候，能切多少个蛋糕

输入第一行一个整数 \(T\) ,代表有 \(T\) 组测试数据

接下来 \(T\) 行，每一行输入 $2$ 个数 \(n\) 和 \(m\)

$1\le T \le10^4$

$1\le n,m\le10^6$

对于每一组测试数据，输出对应答案