问题 G: 蛋糕上的草莓是蛋糕的灵魂

内存限制:256 MB 时间限制:20 S
题面:传统 评测方式:文本比较 上传者:
提交:6 通过:2

题目描述

草莓蛋糕的灵魂是蛋糕上的草莓。

现在有 x 块大小相同的草莓和 y 块大小相同的蛋糕。Mobiusp 可以选择把所有草莓堆放在一起并且切 n(n>0) 刀,将每个草莓切成大小相同的 2n2n 块,总共得到 2nx 块大小相同的草莓,每块草莓的大小是原来的 1/2n。当然,也可以一刀也不切,保留原来的 x 块草莓。

同理,可以选择把所有蛋糕堆放在一起切 m 刀,得到大小相同的 2my 块蛋糕,或者一刀也不切。

现在,Mobiusp 需要为蛋糕分配草莓,并满足以下条件:

  • 每块蛋糕上至少有一块草莓

  • 每块蛋糕上的草莓块数相同

请你设计一种切开草莓和蛋糕,并将草莓分配给每块蛋糕的方案,优先保证每个草莓的大小最大,再保证每个蛋糕的大小最大,输出最终蛋糕的个数与每个蛋糕上的草莓的个数。草莓和蛋糕必须用尽,不能丢弃。







输入格式

第一行一个整数 t ,表示有t 组数据 (1t105)

接下来 t 行,每行两个整数 x 和 y (1x,y1012),分别表示草莓的个数与蛋糕的个数

输出格式

对于每组数据输出一行

每行两个整数用空格隔开,分别表示蛋糕的个数与每个蛋糕上草莓的个数

输入样例 复制

2
2 8
10 5

输出样例 复制

8 1
5 2