Description

Alice是个美丽又聪明的女孩，Bob很想跟她玩。

有一天，Alice拿着一个很大的长方形布块，想把它裁剪成若干小正方形。问题是，如果所有的正方形都是同一个尺寸，那么，这个尺寸到底能达到多大呢？

对Alice来说，这虽是个简单的问题，但是她事情多，所以想请Bob帮忙。

Alice这么可爱，Bob能不帮吗？可是Bob并不聪明，尤其害怕数学，所以，心有余力不足的Bob想要请你这个编程天才帮忙了，呵呵。

Alice会告诉Bob一些长方形布块的长与宽，Bob则必须告诉Alice能裁剪出若干小正方形的最大尺寸。

难弄的是所有长方形布块的尺寸都是用二进制表示的，而且Bob的答案也必须用二进制数的。

Input

第一行有一个正整数，表示有几个长方形需要裁剪。 每个长方形包括一对整数A、B（0<a,b<2^1000），表示长和宽。

Output

每个长方形应以一行的形式，输出一个二进制数，来表示能裁剪到上述描述中的最大小正方形的边长。

Sample

Input

2
100 1000
100 110

Output

100
10

Source: qn