P14958 [HackerEarth] Ankita is a maths whiz. Powers of large numbers have fascinated her for a long time. She loves them so much that when she sees two numbers A and B, she tries to find out all the odd digi
普及-
题目描述

Ankita is a maths whiz. Powers of large numbers have fascinated her for a long time. She loves them so much that when she sees two numbers A and B, she tries to find out all the odd digits in the number A raised to the power of B i.e.
A^B. However she is feeling adventurous today and wants to write a program to do this for her. Being the expert programmer, you decide to help her.

Note: Only C language is allowed.

Input Format
The first line consists of the number of test cases T. Each of the following T lines thereafter comprises two numbers A and B.

Output Format
In each of the T line, print an integer N. Here, N is the number of digits that are odd in A raised to the power of B (A^B).

Constraints

1 ≤ T ≤ 10^6
1 ≤ A ≤ 500
1 ≤ B ≤ 80

SAMPLE INPUT
2
5 4
3 3

SAMPLE OUTPUT
1
1

Explanation

Let's say the number A=153, B=2. So, the output should be the number of odd digits in 153^2.

输入格式

见题面

输出格式

见题面

样例输入
1000 366 46 281 52 49 28 54 58 224 9 467 56 354 68 11 14 492 53 304 75 245 22 176 75 420 31 258 64 47 29 439 26 33 34 152 78 448 54 318 3 41 17 167 31 71 27 9 43 402 41 354 42 161 12 243 71 401 28 9 8 459 16 155 16 440 51 267 68 209 31 411 15 494 42 493 47 382 36 255 36 385 47 244 24 44 37 275 14 118 64 480 58 329 20 436 59 62 35 396 45 126 40 127 46 322 63 76 72 418 43 209 75 373 72 3 29 93 60 226 30 149 79 246 69 184 40 81 67 194 7 424 8 142 3 201 71 238 41 111 62 277 38 179 39 162 45 60 35 459 41 47 56 372 42 455 10 461 34 220 9 494 28 271 39 442 78 204 21 461 71 347 68 367 5 468 6 235 51 453 16 84 61 239 76 311 63 94 11 328 69 315 30 449 70 34 6 363 38 298 27 144 50 184 32 274 6 180 18 405 69 195 11 271 69 64 51 415 41 428 73 229 38 184 18 447 34 104 56 29 50 125 55 146 55 235 68 81 13 78 52 200 19 46 37 359 32 172 29 191 18 319 48 326 18 420 36 383 80 337 32 350 65 451 11 406 59 294 9 22 13 36 39 15 13 208 29 263 18 30 58 33 8 146 60 334 66 113 15 49 42 402 24 334 2 165 17 487 17 223 37 227 4 242 53 248 15 485 77 185 68 266 24 254 34 17 6 93 53 293 14 456 64 290 1 170 4 131 15 343 43 389 1 128 22 167 73 188 66 213 10 322 54 123 51 108 31 458 74 210 71 184 74 363 35 393 15 233 27 360 80 326 1 66 5 346 47 280 63 8 52 170 33 54 34 457 29 447 15 107 56 391 77 122 52 288 29 46 24 298 71 475 62 407 14 432 55 135 20 2 13 333 25 68 71 451 29 172 54 111 33 279 34 421 38 102 8 414 46 325 43 237 10 279 17 458 33 472 14 198 62 57 31 281 52 211 40 422 67 381 49 120 36 13 66 467 24 76 73 491 43 223 24 18 75 400 30 434 49 334 24 378 20 464 69 493 44 266 58 424 63 212 73 104 45 362 64 127 6 222 76 383 79 310 39 298 51 228 44 379 9 128 18 62 9 41 53 182 79 291 28 500 3 194 37 240 54 313 18 332 12 211 15 68 26 277 40 65 47 301 54 464 52 381 70 103 10 463 1 94 72 382 74 278 37 478 55 32 50 267 42 266 77 16 41 117 16 171 61 202 33 194 64 89 14 146 71 128 53 100 55 410 33 177 47 448 30 298 45 394 34 150 43 306 49 426 50 445 79 496 38 66 46 297 37 53 35 50 70 174 78 44 26 20 45 158 75 270 6 400 57 50 11 338 73 326 71 267 79 92 69 301 78 450 80 219 60 241 13 209 55 88 50 500 5 363 6 77 17 203 64 143 4 278 24 140 47 500 69 302 10 410 54 333 10 485 24 4 31 338 31 78 63 282 22 80 15 492 45 220 54 37 61 400 47 367 56 197 58 422 51 312 76 135 15 313 32 26 52 119 58 152 18 465 34 57 9 302 68 386 11 178 8 174 54 240 14 3 44 96 54 26 42 282 31 242 14 262 62 117 59 197 55 448 77 384 44 178 50 27 28 121 19 427 1 140 53 323 42 272 14 58 5 152 53 225 1 266 52 146 26 401 40 430 5 467 38 446 27 147 70 196 67 116 2 275 4 480 53 457 6 114 37 379 12 120 55 389 19 36 23 172 59 8 8 150 56 156 27 469 65 278 72 61 80 204 77 44 55 383 2 130 32 230 60 100 48 354 4 379 66 96 40 343 77 199 76 11 59 339 33 354 42 221 80 131 50 366 66 332 52 493 4 190 64 469 69 487 6 389 75 216 63 423 66 114 40 466 80 129 7 422 40 326 2 256 59 367 8 42 66 335 40 153 4 370 59 144 60 236 69 366 56 60 59 419 64 123 9 347 75 121 32 31 36 236 80 484 40 352 34 1 43 433 35 444 17 2 21 465 13 365 37 197 27 1 8 53 34 275 17 91 61 260 48 334 25 247 57 286 41 53 10 83 20 500 57 77 30 354 33 135 51 349 54 378 32 31 58 214 49 103 28 323 30 137 2 74 58 111 10 316 60 205 63 31 1 208 27 125 47 186 51 374 69 434 6 51 46 2 27 249 80 19 22 392 57 313 5 29 37 124 18 191 47 201 3 109 63 313 21 175 34 251 31 373 36 20 14 470 33 255 69 112 24 498 70 150 36 464 71 287 38 280 79 464 70 173 1 328 53 248 39 479 44 102 49 399 1 11 61 294 41 132 21 87 53 229 79 101 1 450 4 48 57 359 11 289 75 491 49 369 38 228 67 104 64 19 63 131 20 468 38 227 62 486 6 488 28 109 23 445 77 335 35 197 65 306 7 480 75 463 57 453 40 465 53 218 17 242 9 390 32 138 67 402 53 411 28 347 15 405 3 40 30 221 49 449 25 263 9 186 20 212 31 34 30 405 45 421 48 163 62 172 6 261 44 466 56 358 67 290 54 461 39 262 21 354 31 346 29 293 23 321 14 73 32 162 28 339 80 231 25 386 47 165 48 399 32 111 45 46 47 43 41 189 17 53 58 423 26 42 18 323 73 314 33 180 6 318 6 110 12 413 3 43 54 246 55 118 71 105 67 442 21 220 36 150 10 262 75 35 67 108 51 347 72 63 59 295 49 472 46 461 74 257 21 475 33 140 42 147 28 282 44 333 50 376 47 65 18 89 22 253 50 203 77 37 7 338 7 401 8 203 31 10 59 453 57 13 47 98 56 438 76 246 44 176 42 276 11 424 72 198 4 215 42 415 21 385 13 157 1 413 31 242 69 493 19 11 1 258 46 48 77 141 32 149 37 247 76 161 25 43 36 182 18 189 32 387 56 354 73 328 1 260 63 343 22 120 77 83 50 467 47 25 7 439 2 192 35 400 11 104 16 348 1 384 72 48 10 8 44 279 53 327 48 320 64 71 19 343 40 471 35 156 11 431 78 470 73 1 56 358 64 113 41 490 9 3 76 412 15 255 6 278 43 107 42 131 42 145 22 378 50 180 46 461 59 330 79 176 48 61 60 121 17 234 24 368 34 149 77 288 29 315 41 13 23 449 50 133 45 422 41 195 50 398 8 328 58 165 42 25 39 392 10 257 43 66 34 39 70 351 19 259 47 385 29 420 74 220 56 398 38 96 45 142 18 161 65 240 9 108 55 199 15 465 22 125 18 457 15 50 34 163 68 416 49 292 32 440 23 234 68 474 66 423 28 377 2 494 46 389 39 101 73 351 69 63 1 354 18 245 34 244 33 272 3 58 27 167 68 160 54 436 25 456 50 366 64 500 27 196 41 424 57 304 11 15 66 402 37 211 66 404 20 222 67 11 79 62 46 433 58 65 59 418 21 487 58 87 41 388 44 183 19 185 65 107 55 28 49 349 68 27 42 193 19 305 12 79 42 175 35 53 71 256 18 421 67 256 1 242 44 471 34 441 55 170 76 465 76 413 61 133 71 82 32 176 75 364 21 418 65 93 58 80 35 428 29 217 36 17 26 410 8 127 62 276 48 414 23 163 35 444 44 497 65 234 39 98 58 183 55 229 79 433 54 466 33 55 40 170 11 281 45 170 48 383 60 5 71 48 18 448 6 296 37 30 19 466 30 318 1 14 7 389 38 212 45 184 39 488 64 454 14 289 49 334 15 352 42 410 19 58 19 360 11 177 67 401 74 158 76 306 10 132 21 108 80 486 13 464 65 404 77 191 68 497 66 207 54 478 54 293 26 78 52 491 44 83 50 391 68 194 22 34 54 242 74 22 47 309 48 78 20 40 9 246 74 213 45 152 27 375 26 295 16 413 73 263 27 114 20 224 31 344 9 51 35 341 63 39 43 373 79 260 13 494 72 346 44 465 14 490 7 45 47 23 53 61 55 177 58 309 63 443 50 252 8 272 44 251 1 411 23 1 43 47 19 405 41 312 39 280 62 485 20 191 64 423 44 65 9 131 17 58 24 88 8 186 69 489 63 351 58 157 24 295 78 362 80 270 34 54 78 464 29 290 56 208 8 364 50 67 25 75 37 152 2 183 65 209 58 110 18 233 69 183 20 455 55 231 16 54 41 376 30 397 1 339 6 155 18 464 37 189 59 399 30 156 35 321 40 48 3 242 50 59 26 137 57 190 80 8 58 118 29 239 8 414 32 60 20 297 32 89 71 310 35 409 40 206 8 161 28 330 12 413 27 471 66 309 10 17 11 244 64 236 3 420 9 256 10 246 39 237 79 321 35 469 56 140 37 341 26 198 30 160 36 430 21 4 33 55 69 301 39 150 31 362 78 217 2 476 49 409 7 88 38 191 66 151 74 308 35 250 73 438 2 51 11 184 17 286 18 249 2 271 41 100 61 395 19 170 5 52 43 115 80 456 20 138 77 461 12 256 50 417 48 284 76 82 21 391 70 290 51 437 78 318 62 281 80 22 11 87 80 438 35
样例输出
35 35 31 72 6