哪一对共同部分最大

题目描述

给定 n 组正整数，每组包含 ai、bi。计算每一组的最大公因数，选择最大公因数最大的一组；若多组并列，选择输入位置最靠前的一组。

输入格式

第一行输入整数 n，满足 1≤n≤100。接下来 n 行，第 i 行输入 ai、bi，满足 1≤ai,bi≤5000。

输出格式

输出两个整数，依次为选中组的编号（从 1 开始）和该组的最大公因数。

样例

输入

3
18 24
24 36
40 56

输出

2 12