TopCoder

User's AC Ratio

82.4% (14/17)

Submission's AC Ratio

30.0% (42/140)

Description

第二天,你到了約定的櫻花樹下。(詳情請見TOIJ 1873)
你,妹可,今天也努力的想變成溫拿。

「疑?我好像再哪裡看過那個女生?」你看著樹下的金髮小蘿莉。
「喔膩醬!你終於來了!」
「這句話我好像聽過?奇怪,頭好痛...」
「吶,喔膩醬,跟我定下契約吧!」
「甚麼契約!?好像很麻煩?」
「如果定了契約的話,喔膩醬想對我做甚麼都可以喔!」
「那我們快點吧!」
「總之,喔膩醬,一起回家吧!」
「哦哦...」
「對了!喔膩醬,我的名子是櫻(さくら)喔!」

回到家裡後...,
「喔膩醬,你應該沒有跟別人定過契約吧?」
「沒有。」
「那我們就開始吧!」
...
「喔膩醬,這樣契約就完成了喔!」
「嘿嘿嘿,那...疑?」你轉身看見夏梨。
「喔!膩!醬!...你明明就答應過我,你只會跟夏梨定契約的,嗚嗚...」
「疑,有...嗎...」你發現夏梨的瞳孔開始失去顏色...「有!有!有!絕對有這件事。」
「那喔膩醬你為甚麼又跟這個偷腥貓定契約!!!!」
「疑...這個嘛...」
「喔膩醬....夏梨明明這麼相信喔膩醬......」
「等等!夏梨!妳聽我解釋......!」
「喔膩醬!.......最討厭了......!!!」

話說要知道在天龍國定下契約是種很麻煩的東西,假設出生那天是第1天,在第n天定下契約之後,每到n,2n,3n,4n...天都必須進行一次儀式(定下契約那天也算是一次儀式),比如帶契約者去逛街看電影,買禮物送她,或是和她共進燭光晚餐之類的,不然你可能就會被契約者OOXX。
假設你,妹可,從出生那天就每天都和人定下新的契約,那請問某一天你需要進行多少次儀式呢?

Input Format

輸入第1行有一個整數N,代表總共有N比詢問。
接下來每一行有一個正整數A,代表詢問。

對於所有測資,
測資1,滿足1≤N≤10,1≤A≤10
測資2,滿足1≤N≤1000,1≤A≤1000
所有測資,滿足1≤N≤106 ,1≤A≤107

Output Format

對於每個詢問,輸出妹可在第A天需要進行的儀式的次數。

Sample Input

5
1
2
3
16
36

Sample Output

1
2
2
5
9

Hints

在那之後,你追了出去,但是你已經看不見夏梨的身影了。

Problem Source

2015年建中校內培訓第七次模擬賽

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 30
For Testdata: 2 ~ 3, Score: 60
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536