시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 256 MB | 2 | 1 | 1 | 50.000% |
เป็นที่ทราบกันโดยทั่วไปว่ากระต่ายชอบกินแครอทที่สุด ซึ่งไม่จริงเพราะกระต่ายชอบกินผักใบเขียวและหญ้ามากกว่า ดังนั้นส าหรับฝูงกระต่ายแล้วการกินแครอทจึงเป็นไปอย่างน่าเบื่อ ฝูงกระต่ายจึงคิดเกมหนึ่งขึ้นมาดังนี้
ในตอนเริ่มต้นมีแครอทอยู่ N ชิ้น กระต่ายในฝูงจะเข้าแถวตามล าดับความน่ารัก โดยกระต่ายแต่ละตัวจะต้องแบ่งแครอทออกเป็นกองกองละเท่าๆกัน และแครอทแต่ละกองจะต้องมีมากกว่าหนึ่งชิ้น ถ้าแบ่งได้ตั้งแต่สองกองขึ้นไปกระต่ายตัวนั้นจะกินแครอทเพียง 1 ชิ้น แต่ถ้าแบ่งไม่ส าเร็จจะต้องกินแครอทถึง 2 ชิ้น (ยกเว้นกรณีที่เหลือแครอทเพียงชิ้นเดียว) ในฝูงมีกระต่ายเยอะกว่าจ านวนแครอทมาก และกระต่ายทุกตัวแบ่งแครอทเก่งมาก (ถ้ามีวิธีแบ่งได้ กระต่ายทุกตัวจะสามารถแบ่งได้อย่างแน่นอน) ถามว่ามีกระต่ายกี่ตัวที่ต้องกินแครอท
บรรทัดแรกเป็นจ านวนกรณีทดสอบ T ชุด (1 ≤ T ≤ 1 000 000)
ถัดมา T บรรทัดเป็นจ านวนแครอท N ชิ้น (1 ≤ N ≤ 10 000 000)
ส าหรับแต่ละกรณีทดสอบ ให้แสดงค าตอบ 1 บรรทัด เป็นจ านวนเต็ม 1 จ านวน แสดงจ านวนกระต่ายที่ต้องกินแครอท
3 1 10 100
1 7 76