#B1012. 浣熊的小溪

浣熊的小溪

题目背景

“从太阳里奔来,又迎着阳光走去;张开熊爪,与风相拥,离别之际,却低首自吟。” 那梦枫畔嬉戏的成长,那阳光下不羁的信仰,历久弥坚,在无数浣熊的心畔回响。 可叹,灵溪上畔,一人意志,大小工事,割裂了纯真的年华,刀刻了落寞的隔阂。 那明澈的小溪,那快乐的往日,还会,在感怀中驻足吗……

题目描述

浣熊岭的森林可以看作一张 n×mn \times m 的网格图。工厂排放的废水污染了纵贯森林的梦枫溪(一条直线),导致所经区域对浣熊是有害的。小浣熊 CleverRaccoon 为了研究废水对浣熊的危害,要寻求你的帮助。

f(n,m)f(n,m) 表示一条直线最多能穿过 n×mn\times m 的网格图的格子数。

小浣熊有两种问题想要问你:

  1. 给定 n,mn,m,求 f(n,m)f(n,m)
  2. 给定 n,m,Qn,m,Q,你需要找到 nn,mmn'\ge n,m'\ge m,满足 f(n,m)Qf(n',m')\ge Q,且 n×mn'\times m' 尽可能小。求 nmnmn'm'-nm 的最小值998244353998244353 取模的结果。数据保证 f(n,m)<Qf(n,m)<Q

输入格式

本题包含多组测试数据。

第一行,输入一个正整数 TT,表示有 TT 次询问。

对于每次询问:

第一行,输入一个正整数 opop,表示问题类型。

第二行,若 op=1op=1,输入 22 个正整数 nnmm;若 op=2op=2,输入 33 个正整数 nnmmQQ

输出格式

TT 行,对于每次询问:一行输出 11 个正整数,表示对应问题的答案。

样例

2
1
2 3
2
2 3 10
4
12

提示

样例解释 #1

对于第一次询问:

下图所示的情况是一种最佳构造方案,梦枫溪穿过 2×32 \times 3 的网格森林时,最多穿过 44 个小网格(黄色部分为穿过的网格,灰色部分为未穿过的网格)。

下示方案不是一种最佳方案,梦枫溪是从两个绿色网格中间的一个顶点上穿过的,所以两个绿色区域都没有被穿过。因此梦枫溪只穿过了 33 个小网格。

对于第二次询问:

如下图所示,当 n=2n'=2, m=9m'=9 时,才能使梦枫溪穿过 1010 个网格的情况下,在原基础添加的 nmnmn'm'-nm 个网格是最少的(红色虚线左边是原来的森林,右边是添加的部分)。

数据范围

对于 100%100\% 的数据,保证 1T101 \le T \le 10op{1,2}op \in \{1,2\}1n,m10181 \le n,m \le 10^{18}2n+mQ2×10182 \le n+m \le Q \le 2 \times 10^{18}