本题有对应的hard version，区别仅在数据范围，保证easy version的测试用例集是hard version的真子集，通过困难版本的代码可直接通过简单版本。
小沙学会了影分身之术，他和他的分身们一共101810^{18}1018只小沙现在使用钩爪固定在一个随时间逐渐合拢的悬崖两侧，如果小沙能说出悬崖两侧的距离，那么悬崖就会停止合拢，否则悬崖就会把这群小沙挤死。
具体来讲，一开始小沙们知道的信息为：悬崖两侧的距离不小于lll且不大于rrr。
接下来每个时刻按照顺序依次进行如下操作。
1、询问小沙们是否知道悬崖两侧的距离，若小沙不知道则不能进行回答（小沙不能猜一个答案，你可以认为一旦小沙猜错，悬崖会立刻以光速合拢，压死所有小沙），若小沙们此时知道答案，悬崖立即停止合拢，剩余的小沙全部存活。
2、小沙们选择一只小沙从悬崖的一侧跳向另一侧，且弹跳的距离为xxx，小沙可以自己任意选择xxx的值，若悬崖两侧的距离大于xxx，则这只小沙会摔死，否则这只小沙还活着，还可以进行下一次弹跳。
3、悬崖合拢111个单位，若合拢后悬崖两侧的距离为000，则立即压死所有的小沙。
小沙必须在某一轮操作中进行“回答”并且正确才可以停止悬崖的合拢，并结束所有过程，而不是当他“知道”悬崖的答案时。
如果小沙的运气非常差，那么在最坏的可能下，小沙们使用最优策略，此时至少死亡多少只小沙？
对于第一个样例：
小沙在第一轮直接推理出当前悬崖的长度为111，所以没有小沙会被压死或者跳崖身亡。
对于第二个样例：
如果小沙选择第一轮令x=2x=2x=2这个长度跳崖，虽然此时小沙不会死，但是也没有得到任何有用的信息。
如果小沙选择第一轮令x=1x=1x=1这个长度跳崖，有两种情况，摔死了或者没摔死，如果没摔死，则说明当前悬崖长度就是111。但是由于第一轮在小沙跳崖后，悬崖的尺寸会合拢减少111，此时悬崖完全合并，没有下一轮再让小沙回答悬崖的长度了，导致所有的小沙都被压死了。题目要求“最坏情况”，所以答案为101810^{18}1018。
对于第三个样例：
具体情况同第二个样例，但是此时由于悬崖合拢111个单位后也不会压死所有小沙，所以至多摔死一个小沙，然后小沙在下一轮回答悬崖的长度，然后结束。
对于第四个样例：
如果小沙第一轮不选择令x=2x=2x=2这个长度跳崖，那么接下来的最坏情况都将导致所有小沙都被压死。类似的，接下来的任意轮中，小沙都会选择x=2x=2x=2这个长度跳崖。