#P18860. [Croatian CPC2025] Hajde Hrabro

[Croatian CPC2025] Hajde Hrabro

Hajde Hrabro

题目描述

将分数 P/QP/Q 写成二进制小数。求其小数部分最多连续出现多少个 00,并给出一段这样的最长连续 00 的起始位置。

小数点后的第一位编号为 11。例如,4/13=0.010011101100‾24/13=0.\overline{010011101100}_2,循环节不断重复,最长的连续 00 有 33 个,可以从小数点后第 1111 位开始。

输入格式

第一行包含整数 TT,表示测试场景数。

接下来 TT 行,每行包含两个整数 P,QP,Q。

输出格式

对每个场景输出一行两个整数,分别表示最长连续 00 的长度和它的一个起始位置。

如果存在多个合法起始位置,可以输出任意一个不超过 10910^9 的起始位置。

数据范围

  • 1≤T≤1001\le T\le100。
  • 1≤P<Q≤1081\le P<Q\le10^8。
  • QQ 为奇素数。

样例 1

输入

5
1 5
3 5
4 13
5 7
24962293 99001627

输出

2 1
2 2
3 11
1 2
23 7649779