文理学院程序设计在线练习


传教士和食人族

Time Limit: 1 Second(s)    Memory Limit: 32 MB

Total Submission(s): 51   Accepted Submission(s): 30
Problem Description

关于过河的智力问题,有许多不同的版本,其中一个版本是关于三个食人族人和三个传教士的。具体描述如下:

有三个食人族人和三个传教士要过河,现在只有一条船,但一次只能载两个人,而无论在河的哪一边,只要食人族人比传教士多,食人族人就会把传教士吃掉。问怎么样才能安全的过河?如果有时间,你可以试试该游戏。



相信这个过河问题对于聪明的你来说应该不太难。为了挑战你的智力,现在我们对这个过河问题进行如下扩展:

1)食人族人和传教士的数量分别为n和m (1 <= n <= m <= 200)

2)船一次最多可以载k个人(k>=2)

3)河的两岸以及船上均需保证传教士人数不少于食人族人数(除非传教士人数为0)

你的任务就是制定最佳策略,利用最少的行船次数,将食人族人和传教士全部安全运送过河。

Input

输入数据首先包含一个整数T,表示测试实例的个数(T<100),然后是T组测试数据。
每组测试包括三个正整数n, m, k.(1 <= n <= m <= 200, 2<=k<=200)

Output

对于每组测试数据,输出最少的行船次数,若无法完成任务,则输出"Sorry".

Sample Input
3
2 2 2
100 100 3
Sample Output
5
Sorry
Source

usx第四届程序设计竞赛