Bittijono

• Time limit: 2.00 s
• Memory limit: 512 MB

Ääretön bittijono on muodostettu aloittamalla jonosta 0 ja lisäämällä joka vaiheessa jonon perään senhetkinen jono niin, että jokainen bitti on käänteinen.

Bittijono alkaa siis muodostua seuraavasti:

• 0
  
• 01
  
• 0110
  
• 01101001
  
• 0110100110010110
  
• 01101001100101101001011001101001
  
• ...
  

Tehtäväsi on vastata $n$ kyselyyn koskien bittijonon sisältöä. Jokaisessa kyselyssä sinulle annetaan kokonaisluku $k$ ja sinun tulee ilmoittaa jonon kohdassa $k$ oleva bitti. Bitit on numeroitu alkaen luvusta 1.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku $n$: kyselyiden määrä.

Sitten syötteessä on $n$ riviä, joista jokaisella on yksi kokonaisluku $k$: kohta bittijonossa.

Tuloste

Tulosta jokaiseen kyselyyn bittijonon kohdassa $k$ oleva bitti.

Esimerkki

Syöte:
3
5
2
7

Tuloste:
1
1
0

Osatehtävä 1 (10 pistettä)

• $1 \le n \le 100$
  
• $1 \le k \le 100$
  

Osatehtävä 2 (19 pistettä)

• $1 \le n \le 10^5$
  
• $1 \le k \le 10^6$
  

Osatehtävä 3 (71 pistettä)

• $1 \le n \le 10^5$
  
• $1 \le k \le 10^{18}$