打牌的贝贝

题号：NC245518
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$BeiBei$ 和 $NingNing$ 在玩一个卡牌游戏，共有 $2n$ 张卡牌，每张牌上都有一个整数，介于 $1$ 和 $2n$ 之间，所有牌上的数字都是不同的。发牌阶段二人都拿到了 $n$ 张牌。每个回合，游戏的过程如下：

若此时 $BeiBei$ 没有牌了，则 $BeiBei$ 判负。
$BeiBei$ 打出一张牌。
然后 $NingNing$ 需要打出一张牌，使得其上的数字比 $BeiBei$ 最新打出的一张牌上的数字大，如果此时 $NingNing$ 无法打出这样的牌，则 $NingNing$ 判负。

容易证明，该游戏总有一方会被判负。 $BeiBei$ 和 $NingNing$ 都足够聪明。考虑所有可能的分牌情况，使他们每个人正好分到 $n$ 张牌。当 $BeiBei$ 和 $NingNing$ 都足够聪明时，求解出其中 $BeiBei$ 、 $NingNing$ 各自获胜的情况数量。

第一行，一个正整数，表示测试数据组数。

每组测试数据一行，包含一个整数。

对于每组数据，输出一行，包含两个整数，分别表示、获胜的情况数量，答案对取模。

示例1

复制

复制