小藍(lán)和小喬正在森林里砍柴，它們有 T 根長(zhǎng)度分別為 n₁, n₂, · · · , n_T 的木頭。對(duì)于每個(gè)初始長(zhǎng)度為 n 的木頭，小藍(lán)和小喬準(zhǔn)備進(jìn)行交替砍柴，小藍(lán)先出手。每次砍柴時(shí)，若當(dāng)前木頭長(zhǎng)度為 x ，需要砍下一截長(zhǎng)度為 p 的木頭，然后換另一個(gè)人繼續(xù)砍，其中 2 ≤ p ≤ x 且 p 必須為質(zhì)數(shù)。當(dāng)輪到某一方時(shí) x = 1 或x = 0 ，它就沒(méi)法繼續(xù)砍柴，它就輸了。它們會(huì)使用最優(yōu)策略進(jìn)行砍柴。請(qǐng)對(duì)每根木頭判斷是小藍(lán)贏(yíng)還是小喬贏(yíng)，如果小藍(lán)贏(yíng)請(qǐng)輸出 1 （數(shù)字 1），如果小喬贏(yíng)請(qǐng)輸出 0 （數(shù)字 0）。

輸入的第一行包含一個(gè)正整數(shù) T，接下來(lái) T 行，每行包含一個(gè)正整數(shù)，其中第 i 的整數(shù)為 ni 。

輸出 T 行，每行包含一個(gè)整數(shù)，依次表示對(duì)于每一根木頭的答案。

3
1
2
6

0
1
1

【樣例說(shuō)明】

對(duì)于 n1 = 1 ，由于當(dāng)前長(zhǎng)度 x = 1 ，小藍(lán)直接輸?shù)簦腾A(yíng)；

對(duì)于 n2 = 2 ，小藍(lán)選擇 p = 2 ，輪到小喬時(shí)當(dāng)前長(zhǎng)度 x = 2 ? 2 = 0 ，小喬輸?shù)?，小藍(lán)贏(yíng)；

對(duì)于 n3 = 6 ，小藍(lán)選擇 p = 5 ，輪到小喬時(shí) x = 6 ? 5 = 1 ，小喬輸?shù)簦∷{(lán)贏(yíng)。

【評(píng)測(cè)用例規(guī)模與約定】

對(duì)于 20% 的評(píng)測(cè)用例，1 ≤ ni ≤ 10³；對(duì)于所有評(píng)測(cè)用例，1 ≤ n_i ≤ 10⁵ ，1 ≤ T ≤ 10⁴