题目描述

饥饿像一只凶猛的野兽,不停地咆哮着,让人无法安宁

​ 大河前有一群野蛮人(共 $n$ 个),每个人都牵着一只羊,饥饿驱使着他们前往河对岸找寻食物。

​ 大河上有一条小船,初始停靠在大河的靠近野蛮人群的这一端,小船最多可以承载 $200$ 公斤的重量,其中每个野蛮人、每只羊都是 $100$ 公斤重,他们需要借助这条唯一的小船共同前往河对岸,乘船过河需要满足以下规则:

  • 小船从大河的一端移动到另一端需要耗时恰好 $1$ 分钟。
  • 小船从河的一端移动到另一端的过程中小船上至少需要有一个野蛮人或者一只羊(羊也掌握了划船的技能)。
  • 当小船到达大河一岸时,小船上的单位(包括野蛮人和羊)都会下船,哪怕这个单位马上又要上船,并且忽略这一步骤的时间。
  • 在任何一个时刻,如果大河的某一岸有羊的存在,并且其中野蛮人的数量大于羊的数量,饥饿会驱使野蛮人杀羊充饥。

​ 请问这群野蛮人和羊是否可以全部顺利活着抵达大河对岸,如果可以,并假设他们耗时 $K$ 分钟,请回答 $K$ 的最小值,如果不可以,输出 $-1$ 。


输入格式

本题有多个样例,第一行一个样例数 $T$ $(1\le T \le 10^5)$。

对于每个样例:

一行一个整数 $n$ $(1\le n \le 10^9)$ ,表示野蛮人的数量和羊的数量。


输出格式

对于每个样例输出一行,如果野蛮人和羊不能全部顺利或者抵达大河对岸,输出 $-1$,否则输出 $K$ 的最小值,共输出 $T$ 行。


样例数据

输入

2
1
2

输出

1
5

备注

对于样例1,一种可行方案是:

第一分钟,一个野蛮人和一只羊乘船抵达大河对岸,耗时 $1$ 分钟。

对于样例2,一种可行方案是:

第一分钟,两个野蛮人抵达对岸,

第二分钟,一个野蛮人回来,

第三分钟,两只羊抵达对岸,

第四分钟,一只羊回来,

第五分钟,一个野蛮人和一只羊抵达对岸,耗时 $5$ 分钟。


操作

评测记录

优秀代码

信息

时间限制: 1s
内存限制: 256MB
评测模式: Normal

题解