Ää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}