11236번 - Carrot 다국어

เป็นที่ทราบกันโดยทั่วไปว่ากระต่ายชอบกินแครอทที่สุด ซึ่งไม่จริงเพราะกระต่ายชอบกินผักใบเขียวและหญ้ามากกว่า ดังนั้นส าหรับฝูงกระต่ายแล้วการกินแครอทจึงเป็นไปอย่างน่าเบื่อ ฝูงกระต่ายจึงคิดเกมหนึ่งขึ้นมาดังนี้

ในตอนเริ่มต้นมีแครอทอยู่ N ชิ้น กระต่ายในฝูงจะเข้าแถวตามล าดับความน่ารัก โดยกระต่ายแต่ละตัวจะต้องแบ่งแครอทออกเป็นกองกองละเท่าๆกัน และแครอทแต่ละกองจะต้องมีมากกว่าหนึ่งชิ้น ถ้าแบ่งได้ตั้งแต่สองกองขึ้นไปกระต่ายตัวนั้นจะกินแครอทเพียง 1 ชิ้น แต่ถ้าแบ่งไม่ส าเร็จจะต้องกินแครอทถึง 2 ชิ้น (ยกเว้นกรณีที่เหลือแครอทเพียงชิ้นเดียว) ในฝูงมีกระต่ายเยอะกว่าจ านวนแครอทมาก และกระต่ายทุกตัวแบ่งแครอทเก่งมาก (ถ้ามีวิธีแบ่งได้ กระต่ายทุกตัวจะสามารถแบ่งได้อย่างแน่นอน) ถามว่ามีกระต่ายกี่ตัวที่ต้องกินแครอท

บรรทัดแรกเป็นจ านวนกรณีทดสอบ T ชุด (1 ≤ T ≤ 1 000 000)

ถัดมา T บรรทัดเป็นจ านวนแครอท N ชิ้น (1 ≤ N ≤ 10 000 000)

ส าหรับแต่ละกรณีทดสอบ ให้แสดงค าตอบ 1 บรรทัด เป็นจ านวนเต็ม 1 จ านวน แสดงจ านวนกระต่ายที่ต้องกินแครอท