#P3330. [ZJOI2011] 看电影

[ZJOI2011] 看电影

题目描述

到了难得的假期,小白班上组织大家去看电影。但由于假期里看电影的人太多,很难做到让全班看上同一场电影。最后大家在一个偏僻的小胡同里找到了一家电影院,但这家电影院分配座位的方式很特殊,具体方式如下:

电影院的座位共有 KK 个,并被标号为 1K1 \sim K。每个人买完票后会被随机指定一个座位,具体来说是从 1K1 \sim K 中等概率随机选取一个正整数,设其为 LL

如果编号 LL 的座位是空位,则这个座位就分配给此人,否则将 LL 加一,继续前面的步骤;如果不存在编号 LL 的座位,则该人只能站着看电影,即所谓的站票。

小白班上共有 NN 人(包括小白自己),作为数学爱好者,小白想知道全班都能够有座位的概率是多少。

输入格式

本题有多组数据。第一行一个整数 TT 表示数据组数,接下来 TT 行每行两个整数 N,KN,K 表示人数和电影院座位数。

输出格式

对于每一组数据数据输出一行两个整数 A,BA,B,表示答案为 AB\frac{A}{B}。你需要保证 gcd(A,B)=1\gcd(A,B) = 1

3
1 1
2 1
2 2
1 1
0 1
3 4

提示

对于 100%100 \% 的数据,1T501 \leq T \leq 501N,K2001 \leq N,K \leq 200