時間制限:1000ミリ秒
メモリ制限:10000KB
問題
THE DRUNK JAILER
酔っ払った看守がn個直列に並んだ刑務所の牢屋のカギを開けたり閉めたりしていく問題。
牢屋のカギは最初全部閉まっている状態から始まる。
牢屋には1~nまでの番号が付いており、最初看守は全ての牢屋のカギを開錠する。
次から看守は、あいてる牢屋に出会ったら鍵を閉め、閉まっている牢屋に当たったら鍵をあける。
看守は2の倍数の部屋だけを選び上記の開錠施錠操作を行う。
次に3の倍数、その次は4の倍数の部屋だけを選び同じ作業を繰り返しこの作業はnの倍数まで続く。
看守が作業を終えた時最終的に鍵の閉まっているドアの数を出力せよ。
入力
一行目にデータセットの数Tが与えられる。
2行目以降はT行続き、各行に一行ずつ牢屋の数Nが与えられる。
牢屋の数は101を超えないと仮定してよい。
出力
看守の作業が終わった時閉められている牢屋の数を出力せよ。
入力の例
2
5
100
出力の例
2
10
出典
Greater New York 2002