Algorithm

A. Candies
time limit per test
1 second
memory limit per test
256 megabytes
Problem link- https://codeforces.com/problemset/problem/1343/A
input
standard input
output
standard output

Recently Vova found n� candy wrappers. He remembers that he bought x� candies during the first day, 2x2� candies during the second day, 4x4� candies during the third day, ……, 2k−1x2�−1� candies during the k�-th day. But there is an issue: Vova remembers neither x� nor k� but he is sure that x� and k� are positive integers and k>1�>1.

Vova will be satisfied if you tell him any positive integer x� so there is an integer k>1�>1 that x+2x+4x+⋯+2k−1x=n�+2�+4�+⋯+2�−1�=�. It is guaranteed that at least one solution exists. Note that k>1�>1.

You have to answer t� independent test cases.

Input

The first line of the input contains one integer t� (1≤t≤1041≤�≤104) — the number of test cases. Then t� test cases follow.

The only line of the test case contains one integer n� (3≤n≤1093≤�≤109) — the number of candy wrappers Vova found. It is guaranteed that there is some positive integer x� and integer k>1�>1 that x+2x+4x+⋯+2k−1x=n�+2�+4�+⋯+2�−1�=�.

Output

Print one integer — any positive integer value of x� so there is an integer k>1�>1 that x+2x+4x+⋯+2k−1x=n�+2�+4�+⋯+2�−1�=�.

Example
input
Copy
7
3
6
7
21
28
999999999
999999984
output
Copy
1
2
1
7
4
333333333
333333328
Note

In the first test case of the example, one of the possible answers is x=1,k=2�=1,�=2. Then 1⋅1+2⋅11⋅1+2⋅1 equals n=3�=3.

In the second test case of the example, one of the possible answers is x=2,k=2�=2,�=2. Then 1⋅2+2⋅21⋅2+2⋅2 equals n=6�=6.

In the third test case of the example, one of the possible answers is x=1,k=3�=1,�=3. Then 1⋅1+2⋅1+4⋅11⋅1+2⋅1+4⋅1 equals n=7�=7.

In the fourth test case of the example, one of the possible answers is x=7,k=2�=7,�=2. Then 1⋅7+2⋅71⋅7+2⋅7 equals n=21�=21.

In the fifth test case of the example, one of the possible answers is x=4,k=3�=4,�=3. Then 1⋅4+2⋅4+4⋅41⋅4+2⋅4+4⋅4 equals n=28�=28.

 



 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include<bits/stdc++.h>
using namespace std;


#define ll long long
#define endl '\n'
#define debug(n) cout<<(n)<<endl;
const ll INF = 2e18 + 99;

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll arr[32];
  for(int i = 0; i < 32; i++){
    arr[i] = pow(2, i+1) - 1;
  }
  ll t;
  cin>>t;
  while(t--){
    ll n;
    cin>>n;
    for(int i = 1; i < 32; i++){
      if(n % arr[i] == 0){
        cout<<(n/arr[i])<<endl;
        break;
      }
    }

  }

}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
7
3
6
7
21
28
999999999
999999984

Output

x
–
+
cmd
1
2
1
7
4
333333333
333333328
Advertisements

Demonstration

Codeforcess solution 1343-A A. Candies ,C++, Java, Js and Python,1343-A

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+