今日题目：归零

Suppose you have an integer vv. In one operation, you can:

·either set v=(v+1)mod32768v=(v+1)mod32768

·or set v=(2⋅v)mod32768v=(2⋅v)mod32768.

You are given nn integers a1,a2,…,an. What is the minimum number of operations you need to make each aiai equal to 0?

Input

The first line contains the single integer n (1≤n≤32768) — the number of integers.

The second line contains nn integers a1,a2,…,an (0≤ai<32768).

Output

Print nn integers. The ii-th integer should be equal to the minimum number of operations required to make aiai equal to 0.

Example

input

4

19 32764 10240 49

output

14 4 4 15

题目分析

题目难度：⭐️⭐️

题目涉及算法：bfs，dp，位运算，贪心，暴力。

ps：有能力的小伙伴可以尝试优化自己的代码或者一题多解，这样能综合提升自己的算法能力

题解报告：

1.思路

这题我用的bfs做的，不是正解接近2s的时间居然能过..

2.代码

#include<bits/stdc++.h>
using namespace std;
const int N = 32768;
int a[N+10];
struct node{
  int z,y;
};
int main()
{
  int n;
  cin>>n;
  while(n--)
  {
    memset(a,0,sizeof(a));
    int t;
    cin>>t;
    queue<node>q;
    q.push({t,1});
    while(q.size())
    {
      node x = q.front();
      q.pop();
      int f = x.z;
      int m = x.y;
      if(a[f])
      {
        continue;
      }
      a[f] = m;
      if(!f)
      {
        break;
      }
      q.push({f*2%N,m+1});
      q.push({(f+1)%N,m+1});
    }
    cout<<a[0]-1<<endl;
  }
  return 0;
}